whatever2507

Bài 1 ngày 1. Gọi Sultan là S cho dễ  . Giả sử số ban đầu là $a$.

Bước 1. S chọn $2$, nếu chưa được thì ta có số $a-2$ lẻ.

Bước 2. S chọn $3$, nếu chưa được thì ta có số $a-5$ chẵn và chia $3$ dư $b (b=1$ hoặc $2)$.

Bước 3. S chọn $5$, nếu chưa được thì ta có số $a-10$ lẻ và chia $3$ dư $b-2$.

Bước 4. S chọn $9$, nếu chưa được thì ta có số $a-19$ chẵn và chia $3$ dư $b-2$.

Bước 5. S chọn $6$, nếu chưa được tức là $b \neq 2$ hay $b=1$, bây giờ ta có số $a-25$ chẵn và chia $3$ dư $2$.

Bước 6. S chọn $4$ nếu chưa được tức là $a-25 \equiv 2 (mod4)$ và bây giờ ta có số $a-29$ chia $3$ dư $1$ và chia $4$ dư $2$.

Bước 7. S chọn $10$, nếu chưa được thì ta còn số $a-35$ chia hết cả $3$ và $4$.

Bước 8. S chọn $12$ và chiến thắng.

 

Đáp số của cả $2$ TH đều là $d \le 10\sqrt{2}$, dùng chung $1$ lập luận và chỉ hơi khác nhau cách đưa quân cờ thỏa mãn .

 

Bài 4 (Tô màu - Nguồn: Đề thi HSG lớp 10 THPT chuyên KHTN). Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau:

i) Tất cả các ô vuông con ở cạnh của bảng đều được tô màu Đỏ.

ii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà $4$ ô vuông con được tô cùng màu.

iii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà hai ô ở mỗi đường chéo đều được tô cùng màu.

Hỏi người ta có thể thực hiện cách tô màu như trên trong các trường hợp với bảng ô vuông kích thước:

$a) 2012 \times 2013?$

$b) 2012 \times 2014?$

 

 Để giải hoàn chỉnh và chặt chẽ bài này ra thì khá dài, thế nên mình chỉ post ý tưởng của câu b ra mọi người thực hiện tính toán nhé . (Còn câu a cách xây dựng thì hoàn toàn không khó   ).

Gợi ý câu 4b)  Giả sử tồn tại cách tô màu thoả mãn điều kiện. Xét các giao điểm của các đường thẳng vuông góc nhau bên trong bảng vuông là các điểm nguyên trên mặt phẳng toạ độ với toạ độ $(i,j) (1 \le i \le 2011, 1 \le j \le 2013)$. Gọi $x_{ịj}$ là số đoạn thẳng đơn vị (đoạn thẳng độ dài $1$) nằm trong hình vuông $4 \times 4$ có tâm là điểm $(i,j)$ mà ngăn cách giữa $2$ ô cùng màu, $y_{ịj}$ là số đoạn thẳng đơn vị nằm trong hình vuông $4 \times 4$ có tâm là điểm $(i,j)$ mà ngăn cách giữa $2$ ô khác màu, $X$ là số đoạn thẳng đơn vị nằm trong bảng vuông $2012 \times 2014$ ngăn cách giữa $2$ ô cùng màu, $Y$ là số đoạn thẳng đơn vị nằm trong bảng vuông $2012 \times 2014$ ngăn cách giữa $2$ ô khác màu. Ta tính $X-Y$ theo $2$ cách.

Để ý rằng $x_{ij}=y_{ij} \forall i,j$.

Đầu tiên ta tính $X-Y$ theo tổng $\sum_{i \equiv j (mod2)} (x_{ij}-y_{ij})$ sau đó theo tổng  $\sum_{i \not\equiv j (mod2)} (x_{ij}-y_{ij})$. Có vẻ ta thấy $2$ tổng này bằng nhau và bằng $0$ nhưng với mỗi cách đếm thì có một số cạnh chưa được tính (các cạnh này toàn nằm giữa các ô vuông đỏ trên biên nên dễ đếm thôi), và 2 cách đếm cho ta số cạnh chưa được tính khác nhau nên suy ra mâu thuẫn .

 

Bài 3 (Toán trò chơi-Nguồn: Tournament of the Towns). Trên bảng ô vuông $20$x$20$ mỗi ô có $1$ quân cờ. $A$ chọn một số thực $d$ và $B$ phải đưa mỗi quân cờ đi tới ô cách ô ban đầu nó đứng một khoảng cách ít nhất là $d$ (khoảng cách giữa $2$ ô được tính theo khoảng cách tâm của $2$ ô đó) và mỗi ô chỉ có thể có $1$ quân cờ. Hỏi với điều kiện gì của $d$ thì $B$ có thể thao tác thoả mãn điều kiện trên?

Hỏi tương tự với bảng $21$x$21$

Bài này chỉ dùng duy nhất $1$ nhận xét, tiếc là chưa ai giải.

Giải bài 3. $*$ TH bảng $20 \times 20$:

Xét toạ độ các ô (được tính ở tâm ô) là $(i, j) \forall 1 \le i, j \le 20$. Xét ô $(10, 10)$, giả sử sau bước chuyển quân cờ ở ô này chuyển đến ô $(a,b) (1 \le a,b \le 20, a, b$ không đồng thời bằng $10)$, khi đó khoảng cách giữa $2$ ô là: $\sqrt{(a-10)^2+(b-10)^2} \ge d$.

Do $1 \le a,b \le 20$ nên $|a-10| \le 10, |b-10| \le 10 \Rightarrow d \le 10\sqrt{2}$.

Cách chuyển quân: Các quân ở các ô $(i, j)$ đến ô $(i', j')$ với $\begin{cases} i'=i+10 & \text{ if } i \le 10\\ i'=i-10 & \text{ if } i > 10 \end{cases}$.

$*$ TH bảng $21 \times 21$: Lập luận tương tự với ô $(11,11)$, cách xây dựng mọi người tự tìm nhé .

Bài 9: (tập hợp,Germany 1970) Cho tập $M$ có $22222$ phần tử .Hỏi $M$ có hay không 50 tập con thoả mãn :

 1/Mỗi phần tử của $M$ là phần tử của ít nhất 1 trong các tập con.

 2/Mỗi tập con đều có $1111$ phần tử.

 3/Với 2 tập $M_i;M_j (i \neq j)$ có ${M_i} \cap {M_j}$ 22 phần tử.

Giải bài 9. Gọi các phần tử của $M$ là $a_1 \rightarrow a_{22222}$. Giả sử tồn tại $50$ tập con $M_i (1 \le i \le 50)$ thoả mãn $3$ yêu cầu trên. Ta đếm số cách chọn $2$ tập $M_i, M_j (i \neq j)$ kèm theo $1$ phần tử $a_k$ thuộc $M_i \cap M_j$. Gọi số cách chọn này là $S$.

Có $C^2_{50}$ cách chọn $2$ tập $M_i, M_j (i \neq j)$ và $22$ cách chọn phần tử $a_k$ thuộc $M_i \cap M_j$.

$\Rightarrow S=22.C^2_{50}=26950$.

Mặt khác, giả sử $a_i$ thuộc $r_i ( \forall 1 \le i \le 22222)$ tập $M_j$. Khi đó dễ CM được $$\sum_{i=1}^{22222}r_i= \sum_{i=1}^{50} |M_i|=50.1111=55550$$.

Có $22222$ cách chọn phần tử $a_i$ bất kỳ, và có $C^2_{r_i}$ cách chọn 2 tập $M_j, M_k$ sao cho $a_i \in M_j \cap M_k$ (coi $C^2_1=0$).

$\Rightarrow S=\sum_{i=1}^{22222} C^2_{r_i}$

$=\sum_{i=1}^{22222} \frac{r_i(r_i-1)}{2}$

$=\frac{1}{2}(\sum_{i=1}^{22222}r_i^2 - \sum_{i=1}^{22222}r_i)$

$\geq \frac{1}{2} (\frac{(\sum_{i=1}^{22222} r_i)^2}{22222}-\sum_{i=1}^{22222} r_i)$ (BĐT C-S)

$=\frac{55550^2-22222.55550}{2.22222}>26950=S$ (mâu thuẫn).

Vậy không tồn tại $50$ tập con của $M$ thoả mãn đề bài.