Diễn Đàn MathScope - Xem bài viết đơn

**huynhcongbang** · 27-01-2016, 03:53 AM

Trước hết, ta sẽ chứng minh rằng số các ô có thể chọn sẽ không vượt quá $p^3$.

Xét một cách chọn các ô trên bàn cờ thỏa mãn điều kiện.

Ta sẽ đếm số $S$ gồm các bộ $(A,B,C)$ mà hai cột $A,B$ và hàng $C$ giao nhau tại hai ô được chọn. Ta sẽ đếm đại lượng này bằng 2 cách:

(1) Đếm theo hai cột $A,B$:
Số cách chọn hai cột như vậy là $C^2_{p^2}$ và rõ ràng có không quá một hàng $C$ tương ứng cắt 2 cột tại hai ô được chọn (theo giả thiết) nên $S \le C^2_{p^2}$.

(2) Đếm theo hàng:
Gọi $x_i$ là số ô được chọn ở hàng thứ $i$, suy ra số các cặp $2$ ô được chọn cùng một hàng là $$S=\sum_{i=1}^{p^2}C^2_{x_i}.$$
Gọi $k$ là số lượng lớn nhất các ô có thể chọn thì $\sum_{i=1}^{p^2} x_i = k$.

Dễ thấy hàm $f(x)=C^2_x$ "lồi" (được hiểu là $f(2x)+f(2y) \ge 2f(x+y)$) nên ta chứng minh được $$S = \sum_{i=1}^{p^2} C^2_{x_i} \ge \frac{1}{2}(\frac{k^2}{p^2}-k) .$$ Từ đó suy ra: $$C^2_{p^2} \ge \frac{1}{2}(\frac{k^2}{p^2}-k)$$ Giải BPT này ra, ta được $2k \le p^2+p^2\sqrt{4p^2-3}$. Dễ chứng minh được rằng với $p \ge 1$ thì $1+\sqrt{4p^2-3} \ge 2p$ nên $$2k \ge p^2 \cdot 2p = 2p^3$$ và ta có đpcm.

Ở lời giải trên, tính nguyên tố của $p$ không được sử dụng. Tuy nhiên, khi chỉ ra các ô thỏa mãn, ta cần sử dụng các lớp thặng dư và nghiệm của hệ phương trình đồng dư và $p$ nguyên tố sẽ giúp cho lời giải sáng sủa hơn. Mọi người thử xem nhé.

27-01-2016, 03:53 AM	#2
huynhcongbang Administrator Tham gia ngày: Feb 2009 Đến từ: Ho Chi Minh City Bài gởi: 2,413 Thanks: 2,165 Thanked 4,188 Times in 1,381 Posts	Trước hết, ta sẽ chứng minh rằng số các ô có thể chọn sẽ không vượt quá $p^3$. Xét một cách chọn các ô trên bàn cờ thỏa mãn điều kiện. Ta sẽ đếm số $S$ gồm các bộ $(A,B,C)$ mà hai cột $A,B$ và hàng $C$ giao nhau tại hai ô được chọn. Ta sẽ đếm đại lượng này bằng 2 cách: (1) Đếm theo hai cột $A,B$: Số cách chọn hai cột như vậy là $C^2_{p^2}$ và rõ ràng có không quá một hàng $C$ tương ứng cắt 2 cột tại hai ô được chọn (theo giả thiết) nên $S \le C^2_{p^2}$. (2) Đếm theo hàng: Gọi $x_i$ là số ô được chọn ở hàng thứ $i$, suy ra số các cặp $2$ ô được chọn cùng một hàng là $$S=\sum_{i=1}^{p^2}C^2_{x_i}.$$ Gọi $k$ là số lượng lớn nhất các ô có thể chọn thì $\sum_{i=1}^{p^2} x_i = k$. Dễ thấy hàm $f(x)=C^2_x$ "lồi" (được hiểu là $f(2x)+f(2y) \ge 2f(x+y)$) nên ta chứng minh được $$S = \sum_{i=1}^{p^2} C^2_{x_i} \ge \frac{1}{2}(\frac{k^2}{p^2}-k) .$$ Từ đó suy ra: $$C^2_{p^2} \ge \frac{1}{2}(\frac{k^2}{p^2}-k)$$ Giải BPT này ra, ta được $2k \le p^2+p^2\sqrt{4p^2-3}$. Dễ chứng minh được rằng với $p \ge 1$ thì $1+\sqrt{4p^2-3} \ge 2p$ nên $$2k \ge p^2 \cdot 2p = 2p^3$$ và ta có đpcm. Ở lời giải trên, tính nguyên tố của $p$ không được sử dụng. Tuy nhiên, khi chỉ ra các ô thỏa mãn, ta cần sử dụng các lớp thặng dư và nghiệm của hệ phương trình đồng dư và $p$ nguyên tố sẽ giúp cho lời giải sáng sủa hơn. Mọi người thử xem nhé. __________________ Sự im lặng của bầy mèo