Số bước tối đa

Trên bàn; người ta đặt $20$ tấm thẻ ; ghi số từ $1$ đến $20$
Với 1 bước ; người ta chọn ra $2$ tấm thẻ có sai biệt nhiều hơn $1$ đơn vị ; sau đó viết lại số trên $2$ thẻ này theo cách : Trừ 1 đơn vị từ thẻ có giá trị lớn hơn và cộng 1 đơn vị vào thẻ có giá trị nhỏ hơn để được 2 thẻ mới.
Hãy tính số bước tối đa có thể thực hiện


Trước hết là xét bài toán tổng quát:

QuoteTrên bàn; người ta đặt $1$ tấm thẻ ; ghi số từ $1$ đến $n$

Với 1 bước ; người ta chọn ra $2$ tấm thẻ có sai biệt nhiều hơn $1$ đơn vị ; sau đó viết lại số trên $2$ thẻ này theo cách : Trừ 1 đơn vị từ thẻ có giá trị lớn hơn và cộng 1 đơn vị vào thẻ có giá trị nhỏ hơn để được 2 thẻ mới.

Hãy tính số bước tối đa có thể thực hiện.

Gọi $m$ là số bước tối đa.
Ta sẽ giải bài này bằng ... thống kê, với bảng số liệu thống kê là $1,2, ..., n$
Dễ thấy, sau mỗi bước như trên, giá trị trung bình của bảng số liệu không đổi và bằng $\frac{n+1}{2}$.
Phương sai của bảng số liệu là:
$$\sigma_{0}^2 =\frac{\sum_{i=1}^{n} \left ( i-\frac{n+1}{2} \right )^2}{n} = \frac{1}{4n}\sum_{i=1}^{n}\left [ 4i^2-4(n+1)i+(n+1)^2 \right ]$$
$$=\frac{1}{4n}\left [\frac{4n(n+1)(2n+1)}{6} -n(n+1)^2 \right ]=\frac{n^2-1}{12}$$

Ta sẽ không thể thực hiện thêm bước nào nữa nếu bảng số liệu của ta gồm $n$ số bằng nhau, hoặc chỉ gồm hai giá trị $\left \lfloor \frac{n+1}{2} \right \rfloor, \left \lfloor \frac{n+1}{2} \right \rfloor+1$. Khi đó, phương sai lớn nhất có thể là:
$$\sigma _{m}^2 = \frac{n.\left ( \frac{1}{2} \right )^2}{n} = \frac{1}{4}$$

Sau mỗi bước, phương sai sẽ giảm đi. Sau $m$ bước, phương sai sẽ giảm từ $\frac{n^2-1}{12}$ về không vượt quá $\frac{1}{4}$. Ta cần tìm ra cách để sau mỗi bước, lượng phương sai giảm đi là ít nhất. Khi đó, ta phải thực hiện nhiều bước nhất.

Gọi $a$ và $b$ là hai thẻ bị đổi ở một bước nào đó, $a-b \geq 2$. Độ chênh lệch phương sai trước và sau khi thực hiện bước này là:
$$\Delta\sigma = \frac{a^2+b^2}{n} - \frac{(a-1)^2+(b+1)^2}{n} = \frac{2(a-b)-2}{n} \geq \frac{2}{n}$$
Dấu "$=$" xảy ra khi $a-b=2$
Vậy $m$ là số nguyên dương nhỏ nhất thỏa mãn:
$$\frac{n^2-1}{12}-\frac{2m}{n}\leq \frac{1}{4}\Leftrightarrow m \geq \frac{n(n^2-4)}{24}$$


Với $n=20$ ta có: $m=330$