$\boxed{\text{Bài toán 51}}$ Cho $2014$ điểm trong mặt phẳng sao cho bao lồi của chúng là một bát giác là $8$ điểm của hệ điểm đã cho. Biết không có điểm nào thẳng hàng và bát giác bao lồi ấy có diện tích không vượt quá $1,5 cm^2$. Chứng minh rằng tồn tại ba điểm thuộc hệ trên sao cho diện tích tam giác tạo bởi $3$ điểm ấy không vượt quá $1/2014 cm^2$. $\boxed{\text{Bài toán 52}}$ Cho $A_1,...,A_{100}$ là một tập các tập con của $\begin{Bmatrix} 1,2,3,4,5,6 \end{Bmatrix}$ sao cho với mọi $i, j, k$ phân biệt, ta có $|A_i\cup A_j\cup A_k|\geq 5.$ Tìm giá trị nhỏ nhất của $\sum_{i=1}^{100}|A_i|$ $\boxed{\text{Bài toán 53}}$ ($TST$ Hong Kong $1999$) Các học sinh được phát bài kiểm tra, mỗi môn một bài, trong $n$ ($n\geq 3$) môn học. Biết rằng với mỗi môn học bất kì có đúng $3$ học sinh đạt điểm tối ưu, còn với hai môn tùy ý thì có $1$ học sinh đạt điểm tối ưu cho mỗi môn trong cả hai môn đó. Hãy xác định $n$ bé nhất sao cho từ các điều kiện có thể suy ra có đúng $1$ học sinh đạt điểm tối ưu cho mỗi môn trong $n$ môn học. Spoiler: Lời giải Nếu có một học sinh đạt điểm tối ưu trong $4$ môn thì sẽ đạt điểm tối ưu trong $n$ môn Vậy ta chỉ cần tìm $n$ nhỏ nhất sao cho tồn tại một học sinh đạt điểm tối ưu ở $4$ môn Xét đồ thị $G=\left ( V,E \right )$ với các đỉnh là học sinh, $2$ học sinh có điểm tối ưu chung ở một môn thì sẽ được nối với nhau bởi một cạnh Ta thấy $2$ tam giác bất kì đều có ít nhất một đỉnh chung Xét ba điểm $X_1,X_2,X_3$ lập thành một tam giác Ta cần xây dựng số $n$ nhỏ nhất sao cho tồn tại bậc của một trong $3$ đỉnh trên lớn hơn hoặc bằng $4$ Ta có: $\left \lfloor \frac{n-2}{3} \right \rfloor+1\geq 4$ $\Leftrightarrow n\geq 8$ Vậy $n_{min}=8$ $\boxed{\text{Bài toán 54}}$ Gọi $f\left ( a,b,c \right )$ là số các cách để điền vão các ô trong bảng $a\times b$ bằng các số trong $\left \{ 1;2;...;c \right \}$ sao cho trong bất kì ô nào, số nằm trong ô đó đều lớn hơn hoặc bằng số ở ô trên nó và số ở ô bên trái nó. Chứng minh rằng: $f\left ( a,b,c \right )=f\left ( c-1,a,b+1 \right )$ $\boxed{\text{Bài toán 55}}$ Đặt $21$ điểm trên đường tròn. Chứng minh rằng: có ít nhất $100$ cặp điểm tạo ra cung nhỏ hơn hoặc bằng $120^0$
$\boxed{\text{Bài toán 56}}$ Cho $A$ là tập gồm $n$ phần tử, $A_1,...,A_m$ là các tập con có $3$ phần tử thoả mãn $\left | A_i \cap A_j \right |\leq 1, \forall i \neq j$. Chứng minh rằng: $\exists T \subset A$ thoả mãn: $\overline{\exists }$ $i$ sao cho $A_i\subseteq T,\left | T \right |\geq \left \lfloor \sqrt{2n} \right \rfloor$ Spoiler: Lời giải Gọi $T'$ là tập không chứa $A_i$ sao cho $|T'|$ đạt max. Như vậy, với bất kì tập $T''=T \cup \{x\}$ thì $T''$ chứa $A_i$. Giờ ta sẽ đếm số bộ $(A_i,m,n)=k$ với $m \neq n \in T'$ và $m,n \in A_i$. Vì $|A_i \cap A_j| \le 1$ nên: $k \le C_{|T'|}^{2}$ Mà với mỗi $p \in A\setminus T'$, ta xác định được duy nhất một phần tử thuộc bộ $(A_i,m,n)$. Vậy nên: $k \ge n-|T'|$ Từ đó, ta có: $C_{|T'|}^{2} \ge n-|T'|$. Giải bpt, ta được đpcm. $\boxed{\text{Bài toán 57}}$ Cho một bảng hình chữ nhật kích thước $2\times n$. Mỗi ô ta viết một số thực dương sao cho tổng $2$ số ở cùng cột đều bằng $1$. Chứng minh rằng: ta có thể bỏ mỗi cột một số sao cho tổng các số còn lại ở cùng một hàng không quá $\frac{n+1}{4}$ $\boxed{\text{Bài toán 58}}$ Cho tập $S$ gồm $n$ điểm sao cho $P\in S$ thì có ít nhất $k$ điểm để mỗi điểm cách $P$ một khoảng là $x$ , không có $3$ điểm nào thẳng hàng . Giả sử tồn tại tập trên chứng minh. $k \leq 1 +\left \lfloor \sqrt{2n} \right \rfloor$ $\boxed{\text{Bài toán 59}}$ Cho bảng ô vuông $n \times n$ được tô bằng $2$ màu trắng và đen. Giả sử tồn tại tập $A$ khác rỗng gồm các hàng sao cho bất kì cột nào cũng chứa một số chẵn ô trắng thuộc $A$. Chứng minh rằng: Tồn tại tập $B$ khác rỗng gồm các cột sao cho bất kì hàng nào đều có số chẵn ô trắng thuộc $B$. $\boxed{\text{Bài toán 60}}$ Có hai đống đá có $n$ hòn và đống kia có $k$ hòn. Cứ mỗi phút một máy tự động lại chọn một đống có số hòn đá là chẵn và chuyển một nửa số hòn đá của đống đá được chọn sang đống kia. Nếu cả hai đống đều có số hòn đá là chẵn thì máy sẽ chọn ngẫu nhiên một đống. Nếu trong hai đống số hòn đá đều là lẻ thì máy sẽ ngừng làm việc. Hỏi tồn tại bao nhiêu cặp sắp thứ tự $(n,k)$, với $n$ và $k$ là các số tự nhiên không vượt quá $2013$, để máy tự động sau một khoảng thời gian hữu hạn sẽ dừng?
$\boxed{\text{Bài toán 61}}$ Cho hai đống đá, một đống có $a$ hòn đá, đống kia có $b$ hòn đá. Hai người chơi, mỗi người đến lượt mình được lấy một hòn đá từ một trong hai đống, hoặc lấy phần nguyên của một nửa số hòn đá từ đống thứ nhất, hoặc lấy phần nguyên một nửa số hòn đá từ đống thứ nhất, hoặc lấy phần nguyên một nửa số hòn đá từ đống thứ hai, hoặc lấy từ hai đống số hòn đá như nhau. Người lấy được hòn đá cuối cùng là người chiến thắng. Hãy tìm tất cả các cặp $(a,b)$ trong đó $a\leq 8,b\leq 13$ sao cho người đi sau có chiến thuật thắng. $\boxed{\text{Bài toán 62}}$ Cho $n$ là số nguyên dương lớn hơn 1.Tìm tất cả bộ số nguyên $(a;b;c;d)$ thỏa mãn : $$a^{n}=b^{n}+c^{n}+d^{n}+2005$$ $\boxed{\text{Bài toán 63}}$ Trong $1$ hội nghị có $42$ người nam và nữ.Trong số $31$ người bất kì luôn tìm được $1$ đôi nam nữ quen nhau.Chứng minh rằng trong số $41$ người đó luôn tìm được $12$ đôi nam nữ quen nhau. Spoiler: Lời giải Giả sử trong số 42 người đó không tồn tại 12 đôi nam nữ quen nhau Tồn tại cách sắp xếp các cặp nam nữ quen nhau lớn nhất. Đặt số cặp nam nữ quen nhau là $k$, còn cặp nam nữ quen nhau là $\left ( a_{i},b_{i} \right )$ với $i=\overline{1,k}$ Ta chia tập hợp 41 người thành 2 phần: Phần 1:2k người ứng với k cặp nam nữ quen nhau Phần 2:$42-2k$ người còn lại. Dễ thấy trong $42-2k$ người này không tồn tại đôi nam nữ nào quen nhau Ta tách $11-k$ người trong phần 2(vì $k\leq 11$ nên $11-k$ không âm). Xét $31-k$ người còn lại: Ta thêm k nam vào thì theo giả thiết, tồn tại 1 người nam trong k người nam quen với 1 người nữ của tập hợp $31-k$ người trên. Giả sử người đó là $a_1$ Khi đó $b_1$ không quen người nào trong $31-k$ người này (vì nếu $b_1$ quen người nào trong $31-k$ người này thì tồn tại 1 cách sắp xếp khác có số người quen lớn hơn k, vô lí) Ta tiến hành thay $a_1$ thành $b_1$ và tiếp tục quá trình trên, ta có k nữ đều không quen người nào trong $31-k$ người này. Ta xét tập hợp gồm $31-k$ người này và k nữ, nhận thấy rằng 31 người này không tồn tại cặp nam nữ nào quen nhau, trái với giả thiết. Vậy trong số 42 người đó luôn tồn tại 12 đôi nam nữ quen nhau $\boxed{\text{Bài toán 64}}$ Cho 1 hình chữ nhất có $S=1$.Bên trong có 5 điểm phân biệt sao cho không có 3 điểm nào thẳng hàng và có thể nằm trên biên hình chữ nhật. Có tồn tại hay không 2 tam giác có $S=\frac{1}{4}$(các tam giác có đỉnh là 3 trong 5 điểm trên). Spoiler: Lời giải Xét hình chữ nhật $ABCD$ có diện tích bằng $1$ và có tọa độ các đỉnh như sau : $A(0;0)$ ; $B(2;0)$ ; $C\left ( 2;\frac{1}{2} \right )$ ; $D(0;\frac{1}{2})$ và $5$ điểm thỏa mãn ĐK đề bài : $E(1;0)$ ; $F(\frac{3}{2};\frac{1}{4})$ ; $G(1;\frac{1}{2})$ ; $H(\frac{1}{2};\frac{1}{4})$ ; $I(\frac{1}{2};0)$ Dễ thấy rằng diện tích mọi tam giác có đỉnh là $3$ trong $5$ điểm $E,F,G,H,I$ đều nhỏ hơn diện tích hình thoi $EFGH$ (Lưu ý rằng $S_{FGI}< S_{FGA}=2S_{FGH}=S_{EFGH}$) Mà $S_{EFGH}=\frac{1}{4}$. Vậy không tồn tại hai tam giác thỏa đề. $\boxed{\text{Bài toán 65}}$Cho $A_{i}$ là những tập hợp hữu hạn phần tử $$\left|\bigcup_{i=1}^N A_i\right|= \sum_{1\leq k \leq N}|A_k| - \sum_{1\leq i_1 < i_2 \leq N} |A_{i_1}\cap A_{i_2}|+ \cdots +(-1)^{N-1}|A_1\cap A_2\cap \cdots\cap A_N|.$$Trong đó $\Large\left|X\right|$ là số các phần tử của tập hợp $\Large X$. Spoiler: Lời giải Cho $A_{i}$ là những tập hợp hữu hạn phần tử $$\left|\bigcup_{i=1}^N A_i\right|= \sum_{1\leq k \leq N}|A_k| - \sum_{1\leq i_1 < i_2 \leq N} |A_{i_1}\cap A_{i_2}|+ \cdots +(-1)^{N-1}|A_1\cap A_2\cap \cdots\cap A_N|.$$Trong đó $\Large\left|X\right|$ là số các phần tử của tập hợp $\Large X$.
$\boxed{\text{Bài toán 66}}$ Cho đa giác lồi $2n$-đỉnh: $a_1,...,a_{2n}$, P là một điểm nằm trong đa giác nhưng không nằm trên đường chéo nào. CMR số tam giác có các đỉnh trong $a_1,...,a_{2n}$ chứa điểm P là một số chẵn. $\boxed{\text{Bài toán 67}}$ Cho 1 từ có $n$ âm tiết (VD: từ "đi chơi” có 2 âm tiết). Hỏi có bao nhiêu cách nói lái từ này trong 2 trường hợp : - Mọi cách nói lái đều có thể chấp nhận. - Có một số từ chỉ có thể nhận dấu sắc và dấu năng ( VD:dep, sat, gac…..). $\boxed{\text{Bài toán 68}}$ Cho $n$-giác . Một số đường chéo của $n$-giác thỏa mãn 3 tính chất sau: 1) Không có 2 đường chéo nào cắt nhau (trong đoạn) 2) $n$-giác bị chia thành các tam giác 3) Số đường chéo xuất phát từ mỗi đỉnh đều là số chẵn ( có thể là 0 ) CMR: $3|n$. Spoiler: Lời giải Xét đa giác $A_1A_2...A_n$ Gọi deg$(A_i)$ là bậc của đỉnh $A_i$, dễ thấy deg$(A_i)=2+$ số đường chéo xuất phát từ $A_i$. (Số 2 ở đây là do tính cả 2 cạnh). Ta có $n$-giác bị chia thành các tam giác cạnh là đường chéo không căt nhau nên ta có: Số tam giác tạo thành $\times 180^o$ $=$ Tổng các góc trong n-giác $=(n-2).180^o$. Suy ra : Số tam giác tạo thành là $n-2$. Ta có: - Mỗi cạnh của $n$-giác thuộc duy nhất 1 tam giác - Mỗi đường chéo được vẽ thuộc đúng 2 tam giác. Suy ra : Tổng tất cả các cạnh của các tam giác $=n+2.$(số đường chéo) Mặt khác $\sum deg(A_i)=2n+2.$(số đường chéo). Suy ra: Tổng cạnh tam giác $=3.(n-2)=n+2.$(số đường chéo)$=\sum deg(A_i)-n$. $\Rightarrow \sum deg(A_i)=4n-6$. Ta lại có $deg(A_i)$ là số chẵn dương nên giả sử có $k$ đỉnh không có đường chéo nào thì $4n-6=\sum deg(A_i) \geq 2k+4.(n-k)=4n-2k \Rightarrow k \geq 3$ Vậy có ít nhất 3 đỉnh không có đường chéo nào xuất phát từ đỉnh đó.Giả sử đó đỉnh $A_i$ thì ta có tam giác tạo thành chứa đỉnh đó duy nhất là $A_{i-1}A_iA_{i+1}$.Như vậy ta có quyền loại các đỉnh này ra khỏi đa giác đã cho mà không làm mất đi tính vẽ được của đa giác. Xóa đi 3 đỉnh $deg=2$ ta thu được $(n-3)$ giác vẫn thõa mãn tính chất bài toán.Tiếp tục thực hiện như thế nhiều lần cho đến khi còn $\leq 3$ đỉnh ta sẽ thấy chỉ có khi còn lại 3 đỉnh thì n-giác ban đầu mới vẽ được như bài toán. Vậy n chia hết cho 3. $\boxed{\text{Bài toán 69}}$ Một tập hợp gồm 1985 phần tử là 1985 số tự nhiên đầu tiên được chia làm 6 tập hợp.CM trong 1 tập có chứa ít nhất 3 phần tử(không nhất thiết phân biệt) thỏa mãn số lớn nhất bằng tổng 2 số còn lại. Spoiler: Lời giải Hint: có thể dùng tô màu, hoặc có thể đếm thông thường $\boxed{\text{Bài toán 70}}$ Cho $n$ là số tự nhiên, $(n>2)$ Xét các từ gồm $n$ chữ $n$ chữ $B$ Từ $x_1x_2...x_{2n}$ gọi là thuộc$S(n)$ nếu có đúng 1 đoạn khởi đầu chứa lượng chữ $B$ giống nhau Tính:$ \lim \dfrac{S(n)}{R(n)} $
$\boxed{\text{Bài toán 71}}$ Trong một hình chữ nhật $1999\times 2000$. Ở ô $(i,j)$ ghi số $3\times 2$ hoặc $5\times 2$ rồi đổi dấu tất cả các số ở tất cả các ô trong hình chữ nhật.Hỏi sau một số chẵn lần thực hiện tổng các số trong bảng có thể là 1998 đuợc không? Spoiler: Lời giải Quy nạp theo $n$ (bất biến) và xét đồng dư theo mod 4. Đặt $S(n)$ là tổng sau n bước $n=1, S(n)$ đồng dư với $2$ mod $4$. $n=2,$ khi đổi dấu, tổng $S(n)$ đồng dư với $0$ mod $4$. Quy nạp như thế, với $n$ chẵn thì $S(n)$ đồng dư với $0$ mod $4$. Mà $1998$ đồng dư với $2$ mod $4$ nên không thu đc kết quả. $\boxed{\text{Bài toán 72}}$ Có thể phủ được hay không một bảng hình chữ nhật kích thước $5\times 7$ bằng những hình thuớc thợ ba ô sao cho mỗi ô đều được phủ bởi một số lượng như nhau những hình thước thợ ? $\boxed{\text{Bài toán 73}}$ Tìm số nguyên dương $ x_1,x_2,...,x_n,a_1,a_2,...,a_{n-1}$ với $ a_1<a_2<...<a_{n-1}$ thỏa mãn $ x_1x_2...x_n=1980 $ và $ x_i+\dfrac{1980}{x_i} \forall i=1,2,...,n-1 $ $\boxed{\text{Bài toán 74}}$ Chứng minh rằng không thể dùng $25$ tấm domino cỡ $1\times 4$ để phủ kín bảng vuông $10\times 10$. Spoiler: Lời giải Chúng ta tô màu đen các hình vuông có kích thước $2\times 2$ , (giống như bàn cờ vua) Như vậy sẽ thu được $13$ ô đen và $12$ ô trắng. (Hoặc ngược lại) Mỗi hình chữ nhật kích thước $1\times 4$ khi đặt vào đó luôn có diện tích hai phần đen-trắng bằng nhau. Vì số ô đen $2\times 2$ khác với số ô trăng, tổng diện tích các miền đen khác với tỏng diện tích các miền trắng nên các mảnh $1\times 4$ không thể phủ kín hình vuông $10\times 10$. $\boxed{\text{Bài toán 75}}$ Đối với 1 đồ thị hữu hạn ta có thể xóa 1 cạnh tùy ý trong 1 vòng 4 cạnh tùy ý. Với đồ thị đầy đủ $n$ đỉnh thì việc xóa cạnh có thể kết thúc sau ít nhất bao nhiêu lần? Spoiler: Lời giải Chúng ta tô màu đen các hình vuông có kích thước $2\times 2$ , (giống như bàn cờ vua)
$\boxed{\text{Bài toán 76}}$ Tìm hằng số $C$ nhỏ nhất sao cho với mọi đồ thị hữu hạn $G$ ta có $$g^{3}(G)\le{c\cdot{f^4(G)}}$$ trong đó $g(G)$ và $f(G)$ lần lượt là số các tứ diện, số các tam giác trong G. Spoiler: Lời giải Đặt $V_1,...,V_n$ là đỉnh của $G$ và $E$ là tập cạnh của chúng. Với mỗi $i=1,2,...,n$, đặt $A_i$ là tập hợp các đỉnh được nối với $V_i$ bằng một cạnh, $G_i$ là đồ thị con của $G$ mà tập đỉnh là $A_i$, tập cạnh là $E_i$. Đặt $v_i,e_i$ và $t_i=f\left ( G_i \right )$ là số các đỉnh, cạnh, tam giác trong $G_i$ tương ứng. Số tứ diện và tam giác có đỉnh là $V_i$ lần lượt bằng $t_i$ và $e_i$. Vì vậy: $\sum_{i=1}^{n}v_i=2\left | E \right |$, $\sum_{i=1}^{n}e_i=3f\left ( G \right )$, $\sum_{i=1}^{n}t_i=4g\left ( G \right )$ Vì $e_i\leq C_{v_i}^{2}\leq \frac{v_i^2}{2}$ và $e_i\leq \left | E \right |$, ta có $e_i^2\leq \frac{v_i^2\left | E \right |}{2}$ $\Leftrightarrow e_i\leq v_i \sqrt{\frac{\left | E \right |}{2}}$ $\Rightarrow 3f\left ( G \right )\leq 2\left | E \right |\sqrt{\frac{\left | E \right |}{2}}$ $\Leftrightarrow f\left ( G \right )^2\leq \frac{2\left | E \right |^3}{9}$ Vì bất đẳng thức trên đúng với mọi $G_i$, dẫn đến: $t_i=f\left ( G_i \right )=f\left ( G_i \right )^{\frac{1}{3}}f\left ( G_i \right )^{\frac{2}{3}}\leq \left ( \frac{2}{9} \right )^{\frac{1}{3}}f\left ( G_i \right )^{\frac{1}{3}}e_i$ Suy ra: $4g\left ( G \right )\leq 3\left ( \frac{2}{9} \right )^{\frac{1}{3}}f\left ( G \right )^\frac{4}{3}$ Hay: $g^3\left ( G \right )\leq \frac{3}{32}f^4\left ( G \right )$ Hằng số $c$ nhỏ nhất thoả mãn là $\frac{3}{32}$ Dấu "=" xảy ra khi và chỉ khi $G$ là đồ thị đầy đủ. $\boxed{\text{Bài toán 77}}$ Tại 1 trường ĐH có 10001 SV, các SV tham gia các CLB, 1 SV có thể tham gia nhiều CLB, các CLB nghiên cứu các môn KH, 1CLB có thể nghiên cứu nhiều môn KH.Có $k$ môn KH. Biết rằng: i) mỗi cặp SV tham gia cùng nhau đúng 1 CLB ii) không có SV nào tham gia 2 CLB nghiên cứu cùng 1 môn KH iii) mỗi CLB có lẻ SV tham gia iv) CLB có $2m+1$ SV thì nghiên cứu đúng $m$ môn KH Tính $k$. $\boxed{\text{Bài toán 78}}$ Người ta điền số vào 441 ô vuông của bảng vuông 21*21 sao cho tại mỗi hàng và mỗt cột có không quá 6 giá trị khác nhau được điền vào. Chứng minh rằng có một số xuất hiện ở ít nhất 3 hàng và ít nhất 3 cột của bảng vuông này. Spoiler: Lời giải Gọi "ít hàng" là số mà xuất hiện nhiều nhất 2 hàng, tương tự với "ít cột". Trong số 6 giá trị xuất hiện ở các 1 cột bất kì, có ít nhất 1 giá trị xuất hiện ít nhất 3 lần, do đó, có tối đa 5 giá trị "ít hàng", do mỗi số đó xuất hiện nhiều nhất ở 2 hàng, và có 21 cột, nên số vị trí xuất hiện của 5 số là 21.5.2=210, do đó có tối đa 210 vị trí của "ít hàng", tượng tự cũng có tối đa 210 vị trí của "ít cột". Mà có tới 21.21=441>2.210 nên có ít nhất 1 số không "ít hàng", cũng như "ít cột". $\boxed{\text{Bài toán 79}}$ Cho đường gâp khúc khép kín $n$ đoạn thẳng: Tìm $n$ để đường gâp khúc tự căt mỗi đoạn thẳng của mình tại $k$ điểm ($k$ cho trước) Với mỗi $k$ và $n$ ,tìm số giao điểm. $\boxed{\text{Bài toán 80}}$ Tìm $k$ để tồn tại đường gâp khúc khép kín $n$ cạnh , tự cắt nhau $k$ lần (với $n$ cho trước).
$\boxed{\text{Bài toán 81}}$ Với $m$ là số nguyên dương,cho $s(m)$ là tổng các chữ số của $m$.Với $f(n)$ là số $k$ nhỏ nhất sao cho tồn tại một tập $S$ gồm $n$ số nguyên dương thỏa mãn $X$ của $S$.Chứng minh rằng tồn tại các hằng số dương $0<C_1<C_2$ với $C_1lg(n) \leq f(n) \leq C_2lg(n), \forall n \geq 2$. $\boxed{\text{Bài toán 82}}$ Viết $n$ số tự nhiên trên một đường tròn.Tìm $n$ sao cho với mọi dãy gồm n số tự nhiên ta luôn tìm được hai số cạnh nhau sao cho sau khi xoá chúng đi các số còn lại có thể chia thành hai tập hợp có tổng các phần tử bằng nhau. $\boxed{\text{Bài toán 83}}$ Cho bảng vuông $2n \cdot 2n ( n\in N,n \geq 2 ) $ . Ta điền $2n^2 $ số tự nhiên từ $1 \to 2n^2 $ vào bảng, mỗi số lặp lại hai lần. Chứng minh rằng tồn tại một cách chọn $2n^2$ số tự nhiên từ $1 \to 2n^2$ ,mỗi số một lần sao cho trên mỗi hàng và mỗi cột luôn có ít nhất 1 số được chọn. $\boxed{\text{Bài toán 84}}$ Giả sử rằng có 18 ngọn hải đăng trên vịnh BaTư ,mỗi ngọn trong chúng có thể chiếu sáng được một góc $ 20^0$.Chứng minh rằng có thể chọn hướng chiếu sáng của chúng sao cho toàn mặt vịnh BaTư được chiếu sáng. Spoiler: Lời giải Lấy một điểm B tùy ý trong vịnh. Nối B với các điểm A để tạo thành các tam giác đỉnh B. Các tam giác này không được có điểm trong chung. Ta xét các góc ngoài tam giác tại đỉnh B của các tam giác ấy (Có 9 tam giác). Có tất cả 18 góc ngoài tại đỉnh B, tổng các góc đó không quá 3600. Suy ra tồn tại một góc ngoài tại B không quá 200. Suy ra tồn tại một trong hai góc trong ứng với góc ngoài ấy không quá 100. Suy ra điểm B được chiếu sáng. Vậy mọi điểm trong vịnh được chiếu sáng. $\boxed{\text{Bài toán 85}}$ Giả sử có n điểm phân biệt trên mặt phẳng. Có vòng tròn với bán kính r và tâm O trên mặt phẳng. Ít nhất một trong các điểm nằm trong vòng tròn. Chúng ta làm các hướng dẫn sau đây. Tại mỗi bước chúng ta di chuyển O đến trọng tâm của các điểm trong vòng tròn. Chứng minh rằng vị trí của O là không đổi sau khi một số hữu hạn bước. Spoiler: Lời giải Gọi các tâm hình tròn theo thứ tự di chuyển là $O_1;O_2;...;O_k;...$. Gọi: -Số điểm nằm trong $(O_k;r)$, tổng bình phương khoảng cách từ $O_k, O_{k+1}$ đến các điểm đó lần lượt là $s_k, S_k, S'_k$. -Số điểm nằm trong $(O_k;r)$ và nằm ngoài $(O_{k+1};r)$, tổng bình phương khoảng cách từ $O_{k+1}$ đến các điểm đó lần lượt là $a_k, A_k$. -Số điểm nằm ngoài $(O_k;r)$ và nằm trong $(O_{k+1};r)$, tổng bình phương khoảng cách từ $O_{k+1}$ đến các điểm đó lần lượt là $b_k; B_k$. Ta có: -$s_k+b_k=s_{k+1}+a_k$. -$S'_k+B_k=S_{k+1}+A_k$. -Dựa vào vị trí tương đối của các điểm đối với $(O_{k+1};r)$, ta có $A_k\geq a_kr^2, B_k\leq b_kr^2$. -Áp dụng Lagrange, ta dễ có $S'_k\leq S_k$. Từ đây ta có $S_k-s_kr^2\geq S_{k+1}-s_{k+1}r^2$, dùng đơn biến ta dễ có với $k$ đủ lớn, $O_k\equiv O_{k+1}\equiv O_{k+2}\equiv ...$ hay vị trí của $O$ không đổi. (Q.E.D)
$\boxed{\text{Bài toán 86}}$ Cho $k$ là số nguyên dương và $S_n=\left \{1,2,...,n \right \},(n \geq 3) $. Hàm $f:S_n^k \to S_k$ thỏa mãn: nếu $a,b \in S_n^k$ và chúng khác nhau ở tất cả các vị trí thì $f(a) \neq f(b)$. Chứng minh rằng có $i \in \left \{1,2,...,k \right \}$ sao cho: $$f(a_1,a_2,...,a_k)=a_i ,\forall a=(a_1,a_2,...,a_k)\in S_n^k$$. $\boxed{\text{Bài toán 87}}$ Cho $(O)$ bán kính 1,và $F$ là hình lồi đóng nằm trong $C$(Nghĩa là:Nếu $P,Q$ là các điểm của $F$ thì đoạn thẳng $PQ$ nằm trong $F$;tất cả các điểm biên của $F$ nằm trong $F$;tất cả các điểm của $F$ nằm trong đường tròn $C$.).Hơn nữa giả sử rằng từ mỗi điểm của $C$ có thể vẽ được hai tia tiếp tuyến của $F$ mà góc giữa chúng bằng $60^0$.Chứng minh rằng $F$ là hình tròn bán kính $\frac{1}{2}$. $\boxed{\text{Bài toán 88}}$ Cho 100 điểm là đỉnh của đa giác đều 100 cạnh nội tiếp đường tròn. Lấy trong đó ra 20 điểm, 10 điểm tô màu đỏ, 10 điểm tô màu xanh. Chứng minh rằng tồn tại 2 cặp điểm có độ dài bằng nhau, 1 cặp cùng màu đỏ, 1 cặp cùng màu xanh. $\boxed{\text{Bài toán 89}}$ Cho $m;n;p;q$ là các số nguyên dương và đặt $X=\{ 1;2;...;q \}.$ $M$ và $N$ là các tập con của $X$ thỏa mãn $|M|=m;|N|=n$ và với mọi $i;j$ mà $0\leq i;j\leq q-1$ thì $|(M+i)\cap (N+j)|=p$. Chứng minh rằng: $$mn=pq$$ Với kí hiệu $$A+i=\{ x+i (mod \ \ q) | x \in A \}$$ $\boxed{\text{Bài toán 90}}$ Cho $n$ số $d_1,d_2,...,d_n$. Tìm điều kiện cần và đủ để các số này là bậc của 1 đồ thị a)$n$ đỉnh b)có giả thuyết a và là Đồ thị liên thông. c)có giả thuyết a và có đường đi khép kín đến các đỉnh.
$\boxed{\text{Bài toán 91}}$ "Từ" được định nghĩa là một số có 10 chữ số chỉ gồm các số 0 và 1. Một "phép biến đổi" một từ là chọn một số các chữ số liên tiếp trong từ sao cho tổng của chúng là số chẵn rồi đảo ngược các số đó. Hai từ được gọi là "đồng nghĩa" nếu sau một số lần dùng phép biến đổi từ này có thể biến thành từ kia. Tìm số lớn nhất các từ đôi một không đồng nghĩa. Spoiler: Lời giải Đáp số: $46.$ $\boxed{\text{Bài toán 92}}$ CMR mọi số tự nhiên đều là tổng của 3 số tam giác ( $n= \dfrac{t(t+1)}{2}$ là số tam giác) $\boxed{\text{Bài toán 93}}$ Cho $A=\{x_1;x_2;...;x_n\}$ và không có một số số nào trong A có tổng bằng 0. Chứng minh rằng có thể phân hoạch $\mathbb{N^*}$ thành hữu hạn tập hợp $A_1;A_2;..;A_{k}$ với $|A_i|=+\infty$ sao cho với bất kì $a_1;a_2;...;a_n$ cùng thuộc 1 tập $A_{i}$ nào đó thì $\sum\limits_{i=1}^nx_ia_i$ khác 0. $\boxed{\text{Bài toán 94}}$ Có bao nhiêu cách xếp 8 con xe lên bàn cờ 8x8 ô sao cho không có 2 con xe nào ăn nhau và không có con xe nào nằm trên 1 trong 2 đường chéo của bàn cờ ? Spoiler: Lời giải Có $8!$ cách xếp 8 con xe lên bàn cờ $8\times 8$ sao cho không có 2 con xe nào ăn nhau, và không có hay con xe nào nằm trên 1 trong 2 đường chéo của bàn cờ. Dòng đầu tiên có 8 cách chọn, dòng thứ 2 có 7, tiếp tục thì có 8! Tính số cách xếp 8 con xe lên bàn cờ sao cho chắc chắn có ít nhất một con xe nằm trên đường chéo bàn cờ. - Nếu có ít nhất $i$ con xe nằm trên đường chéo bàn cờ (có $C^i_8$ cách chọn), xóa dòng và cột chứa con xe này thì thu được bàn cờ $(7-i)\times(7-i)$, dùng kết quả 1 thì có $(7-i)!$ cách xếp sao cho không có hai con xe nào ăn nhau. Vậy: $C^i_8.(7-i)!$ Cho $i$ chạy từ $1$ đến $8$ Vậy ta có số cách xếp là $$8!-\sum^8_{i=2}C^i_8(8-i)!(-1)^{i-1}=\sum^8_{i=2}C^i_8(8-i)!(-1)^i=14833$$ $\boxed{\text{Bài toán 95}}$ 1)Cho $X=\{1,2,...,50 \}$ , $k$ là số nguyên dương sao cho mọi tập con gồm $k$ phần tử của $X$ đều có chứa 2 phần tử khác nhau $a,b$ của $X$ sao cho $ab$ chia hết cho $a+b$ .Chứng minh $k>38$. 2)Cho $X=\{1,2,...,2003 \}$, $n$ nguyên dương sao cho 1 tập con gồm $n$ phần tử của $X$ luôn có 1 phần tử là lũy thừa của 2 hoặc có 2 phần tử có tổng là lũy thừa của 2 . CM $n>998$. 3)Cho $X=\{1,2,...,2004 \}$, $n$ nguyên dương sao cho nếu loại bớt khỏi $X$ $n$ phần tử thì tập hợp còn lại không có phần tử nào là tích của 2 phần tử khác . CM $n>42$. 4)Cho $X=\{1,2,...,n \}$, $k$ nguyên dương sao cho trong mọi tập con chứa $k$ phần tử đều có ít nhất 2 số mà 1 trong 2 số đó là bội của số kia . CM $k> \left\lfloor \frac{n+1}{2} \right\rfloor$. Spoiler: Lời giải 1) Xét tập con $S\subseteq X$ . Giả sử $a,b\in S$ và $ab\vdots (a+b)$. Đặt $c=\left ( a,b \right )$. Ta có $a=ca_{1},b=cb_{1},\left ( a_{1},b_{1} \right )=1$. Vì $ab\vdots (a+b)$ nên $c^{2}a_{1}b_{1}\vdots c(a_{1}+b_{1})\Rightarrow ca_{1}b_{1}\vdots(a_{1}+b_{1})$. Do $\left ( a_{1},b_{1} \right )=1\Rightarrow \left\{\begin{matrix} \left ( a_{1},a_{1}+b_{1} \right )=1\\ \left ( b_{1},a_{1}+b_{1} \right )=1 \end{matrix}\right. \Rightarrow a_{1}b_{1}\vdots/(a_{1}+b_{1})$ $\Rightarrow c\vdots (a_{1}+b_{1})$ Có $a+b\leq 99\Leftrightarrow c(a_{1}+b_{1})\leq 99\Rightarrow (a_{1}+b_{1})^{2}\leq 99\Rightarrow a_{1}+b_{1}\leq 9$$a+b\leq 99\Leftrightarrow c(a_{1}+b_{1})\leq 99\Rightarrow (a_{1}+b_{1})^{2}\leq 99\Rightarrow a_{1}+b_{1}\leq 9$ Xét tất cả các khả năng, ta có $23$ cặp số $(a,b)$ thỏa mãn $(6,3);(12,6);(18,9);(24,12);(30,15);(36,18);(42,21);(48,24);(12,4);(24,8);(36,12);(48,16);(20,5);(40,10);(15,10);(30,20);(45,30);(30,6);(42,7);(35,14);(28,21);(40,24);(45,36)$. Xét tập $M=\left \{ 6,12,15,18,20,21,24,35,40,42,45,48 \right \}$. $T=X\setminus M$ Chọn $12$ cặp $(6,3);(12,6);(18,9);(24,12);(30,15);(36,18);(42,21);(48,24);(12,4);(24,8);(36,12);(48,16)$. Vì một tập hợp bất kì gồm $39$ phần tử luôn tồn tại ít nhất $13$ phần tử thuộc các cặp trên nên theo nguyên tắc Dirichlet thì luôn tồn tại ít nhất một cặp. Như vậy trường hợp $k=39$ thỏa mãn. Nếu $k<39$ thì do $\left | T \right |=50-12=38$ nên luôn tồn tại một tập có $k$ phần tử không thỏa yêu cầu bài toán(mà cụ thể là một tập con của $T$) Vậy $k>38$
$\boxed{\text{Bài toán 96}}$ Tập các số nguyên dương đã được phân hoạch thành hai phần $A,B$.Chứng minh rằng với mọi số nguyên dương $n$ tồn tại các số nguyên phân biệt $a,b>n$ sao cho tập $\{a;b;a+b \}$ chứa trong $A$ hoặc $B$. Spoiler: Lời giải Xét 4 số tự nhiên $a,b,c,d>n$ sao cho $a,b\epsilon A$, $c,d\epsilon B$ Giả sử không có sô $a,b$ nào thoả mãn yêu cầu đề bài Ta có: $\left\{\begin{matrix}a+b\epsilon B \\ c+d\epsilon A \end{matrix}\right.$ $\left\{\begin{matrix}a+b+c;a+b+d\epsilon A \\ a+c+d;b+c+d\epsilon B \end{matrix}\right.$ $\left\{\begin{matrix}2a+2b+c+d\epsilon A \\ a+b+2c+2d\epsilon B \end{matrix}\right.$ $\left\{\begin{matrix}\left ( a+b+c+d\right )+\left ( a+b \right )\epsilon A \\ \left ( a+b+c+d \right )+\left ( c+d \right )\epsilon B \end{matrix}\right.$ $\Rightarrow \left\{\begin{matrix}\left ( a+b+c+d\right )\epsilon B \\ \left ( a+b+c+d \right )\epsilon A \end{matrix}\right.$ Vô lí vì $A,B$ rời nhau Suy ra đpcm $\boxed{\text{Bài toán 97}}$ Hãy tìm số $k$ lớn nhất sao cho tồn tại $k$ số thuộc $\{1;2;..;n\}$ và một số bất kì trong $k $ số đó không là ước của $k-1$ số còn lại. Spoiler: Lời giải Trước hết ta xét bài toán đảo: Tìm số $k$ nhỏ nhất sao cho tồn tại $k$ số thuộc tập hợp $X=\{1;2;...;n\}$ sao cho trong $k$ số đó tồn tại hai số $a$ và $b$ sao cho $a\vdots b$. Ta giải bài toán phụ như sau: Xét tập $S=\left \{ a_{1};a_{2};...;a_{k} \right \}\subseteq X$. Biểu diễn $a_{i}=2^{\alpha _{i}}.b_{i},(i=\overline{1,k})$ và $b_{i}$ là những số lẻ. Vì trong $X$ có $\left \lfloor \frac{n+1}{2} \right \rfloor$ số lẻ nên suy ra $k>\left \lfloor \frac{n+1}{2} \right \rfloor$(theo nguyên lý Dirichlet). Trở lại bài toán ta có $k\leq \left \lfloor \frac{n+1}{2} \right \rfloor$. Vậy $max_{k}=\left \lfloor \frac{n+1}{2} \right \rfloor$ $\boxed{\text{Bài toán 98}}$ Vô hạn ô xếp từ trí qua phải.Đánh số các ô 1,2,3,... Rải các viên sỏi vào các ô. Quy tắc chuyển sỏi như sau: - Nếu ô $N$ và $N+1$ đều có sỏi thì chuyển tất cả sỏi ở 2 ô này sang ô $N+2$. -Nếu ô $N+1$ có 2 viên mà ô $N$ và $N+2$ không có sỏi thì chuyển 2 viên đó vào 2 ô $N$ và $N+2$. Chứng minh rằng: 1.Trò chơi kết thúc sau hữu hạn bước. 2.Nếu tồn tại $n$ ô liên tiếp mỗi ô có 1 viên thì trò chơi kết thúc sau $k< n$ bước. $\boxed{\text{Bài toán 99}}$ Cho tập $M$ gồm $n$ số nguyên dương phân biệt .Tìm tất cả $n$ để tồn tại hàm $f(x;x)=0.$ 2) $f(x;y)=0$ thì tồn tại $z\in M ;z \notin \left\{x;y \right\}$ sao cho $$f(x;z)=f(z;y)=1 $$ Spoiler: Lời giải Tìm tất cả n để tồn tại một Turnier n đỉnh (tức là đồ thị có hướng đầy đủ) sao cho: Nếu (A,B) là cạnh thì tồn tại C để (B,C) và (C,A) đều là cạnh Kết quả là chỉ có n=1,2,4 là không thỏa. $\boxed{\text{Bài toán 100}}$ Trong mỗi ô vuông của hình chữ nhật m*n ta viết các số tự nhiên. Một lần ta có thể cộng vào cùng một số nguyên k vào các số ở 2 ô kề nhau sao cho các số sau khi cộng vào là các số nguyên không âm. Tìm điều kiện cần và đủ để tồn tại các cộng sao cho kết quả đạt được là tất cả các ô đều chứa số 0.
