|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
25-01-2016, 09:43 PM | #1 |
+Thành Viên+ Tham gia ngày: Jan 2016 Bài gởi: 15 Thanks: 0 Thanked 4 Times in 2 Posts | Bàn cờ và số nguyên tố Cho số nguyên tố $p$. Chứng minh rằng, trên bàn cờ ô vuông $p^2\times p^2$ có thể chọn được $p^3$ ô vuông, sao cho không có 4 ô nào trong số đó có tâm là đỉnh của hình chữ nhật có cạnh song song với bàn cờ. |
The Following User Says Thank You to Đỗ Minh Khoa For This Useful Post: | namdung (26-01-2016) |
27-01-2016, 03:53 AM | #2 |
Administrator | 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 |
Bookmarks |
|
|