IHateMath

Hiện đã có đề TST January, xin mạn phép đăng để hoàn thiện topic.

Bài 1: Cho số nguyên dương $n$ và $S\subseteq\{0,1\}^n$ là một tập các xâu nhị phân độ dài $n$. Cho một số lượng lẻ các xâu (không nhất thiết phân biệt) $x_1,\, x_2,\, \dots ,\, x_{2k+1}\in S$, ta gọi "đa số" của chúng là xâu $y\in\{0,1\}^n$ sao cho bit thứ $i$ của $y$ là bit xuất hiện nhiều lần nhất trong số các bit thứ $i$ của $x_1,\, x_2,\, \dots ,\, x_{2k+1}$ (ví dụ, khi $n=4$, "đa số" của 0000, 0000, 1101, 1100, 0101 là 0100.)

Giả sử với số nguyên dương $k$ nào đó $S$ có tính chất $P_k$ sao cho đa số của bất kỳ $2k+1$ xâu trong $S$ (có thể có trùng lặp) cũng thuộc $S$. Chứng minh rằng $S$ cũng có tính chất $P_k$ với mọi $k$. 

Bài 2: Cho $ABCD$ là một tứ giác lồi, sao cho nó có hai đường chéo vuông góc nhau tại $H$, và không có hai cạnh kề nhau nào bằng nhau. Gọi $M,\ N$ lần lượt là các trung điểm các đoạn $BC, \, CD$. Các tia $MH$ và $NH$ cắt các đoạn $AD,\, AB$ lần lượt tại $S$ và $T$. Chứng minh rằng tồn tại điểm $E$ nằm bên ngoài $ABCD$ sao cho:

$\quad \bullet$ tia $EH$ chia đôi các góc $BES$, $TED$ và

$\quad \bullet$ $\angle BEN = \angle MED$.

Bài 3: Alice và Bob cùng chơi một trò chơi. Đầu tiên Alice bí mật chọn một tập hữu hạn $S$ các điểm nguyên trên mặt phẳng Đề-các. Sau đó, với mọi đường thẳng $\ell$ trên mặt phẳng mà song song với trục tung hay trục hoành hay có hệ số góc bẳng $\pm 1$, Alice nói cho Bob biết số điểm thuộc $S$ mà $\ell$ đi qua. Bob dành chiến thắng nếu anh ta có thể xác định được $S$. 

Chứng minh rằng nếu Alice chọn một tập $S$ có dạng

$$S = \{(x, y) \in \mathbb{Z}^2 \mid m \le x^2 + y^2 \le n\}$$

với số nguyên dương $m, n$ nào đó, Bob có thể thắng trò chơi này (Bob không hề biết rằng $S$ có dạng trên.)

Mình có ý tưởng cho câu b bài 5, đã đăng lên bên AOPS. Xin đăng lại ở đây; bạn đọc kiểm tra dùm.

Trước hết ta nhận thấy rằng nếu $d=2n-1$ thì tồn tại một bộ số như vậy:

$$n,n-1,n-2,\dots ,3,2,1,2,3,\dots ,n-2,n-1,n$$

Để hoàn tất chứng minh, ta chỉ ra rằng với mỗi $d$ nguyên dương, số $n$ nhỏ nhất sao cho $|S_n(d)|>0$ thì không nhỏ hơn $\frac{d+1}{2}$, bằng quy nạp.

Trường hợp $d=1$ hiển nhiên đúng.

Giả sử $k+1$ là số nguyên dương nhỏ nhất mà mệnh đề trên sai. Khi đó tồn tại một bộ $k+1$-số sao cho $n< \frac{k+2}{2}$. Khi đó phải tồn tại hai chỉ số $i,j$ sao cho $x_i=x_j$ và $|i-j|$ nhỏ nhất có thể. Khi đó mọi số nguyên nằm giữa $x_i,x_j$ chỉ xuất hiện đúng một lần, suy ra phải có một số $m$ nào đó xuất hiện ba lần. Ta thấy rằng bộ $k+1$-số bị cắt thành bốn đoạn (có thể rỗng) bởi $m$:

$$\{S_1\}m\{S_2\}m\{S_3\}m\{S_4\}$$

Câu 4a khá đơn giản. Ta chia mảnh đất thành $10$ hình chữ nhật kích thước $30\times 40$. Khi đó sẽ tồn tại một hình chữ nhật không tâm bồn hoa nào ở phần trong (không kể cạnh của nó). Khi đó phần trung tâm $25\times 35$ của hình chữ nhật này không cắt bồn hoa nào.

Uầy, bài toán rời rạc kia cũ quá rồi (nó là đề thi Liên xô cũ hay một nước đông âu nào đấy). Đã có người hỏi bài này gần một năm trước, xin trích lại câu trả lời:

*Edit: Sau khi đọc kỹ thì thấy hai lời giải hoàn toàn như nhau.

 

Giả sử ngược lại, không có hai điểm nào cùng màu cách nhau 1 đvđd.

Xét một điểm $O$ bất kỳ có màu vàng trên mặt phẳng. Vẽ đường tròn $(O,\, \sqrt{3})$. Lấy một điểm $P$ bất kỳ trên $(O)$. Dựng hình thoi $OAPB$ có cạnh bằng $1$ và có đường chéo là $OP$. Dễ thấy $OA=OB=AB=AC=BC=1$. Theo giả thiết, $A,B$ phải tô khác màu vàng và khác màu nhau. Do đó $P$ phải tô vàng. Từ đây suy ra tất cả các điểm trên $(O)$ phải tô vàng. Điều này trái với giả thiết vì dễ thấy tồn tại hai điểm trên $(O)$ có khoảng cách 1 đvđd.

P/s: Số $1$ có thể được thay bởi bất kỳ số thực dương nào.

Chà chà, anh không có kiến thức về số học đại số nên chịu. Đúng là ban đầu anh cũng có ý tưởng về số nguyên Gauss.