Đến nội dung

Hình ảnh

Giá trị tốt $k=8$ hay $k=10$?

- - - - -

  • Please log in to reply
Chủ đề này có 2 trả lời

#1
tranquocluat_ht

tranquocluat_ht

    Thượng sĩ

  • Thành viên
  • 235 Bài viết

Gọi $S$ là một tập con bất kỳ chứa $k$ phần tử của tập $\{1,2,3,...,24\}.$ Tìm $k$ nhỏ nhất sao cho $S$ luôn chứa ít nhất 2 tập con sao cho mỗi tập con đó chứa 2 phần tử và tổng các phần tử của mỗi tập con bằng nhau.



#2
dungxibo123

dungxibo123

    Sĩ quan

  • Thành viên
  • 330 Bài viết

bài này có phần giống như Đề Olympic 30/4 lớp 10 2016 


myfb : www.facebook.com/votiendung.0805
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~o0o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SỢ HÃI giúp ta tồn tại

NGHỊ LỰC giúp ta đứng vững

KHÁT VỌNG giúp ta tiến về phía trước

Võ Tiến Dũng  

:like  :like  :like  :like  :like 

 

 


#3
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

Với $k=7$, chọn $7$ số trong dãy $Fibonacci$ là $1,2,3,5,8,13,21$, dễ thấy không thoả mãn. Xét $\left | S \right |=8$, giả sử $S$ không thoả mãn đề bài, gọi $K=\left \{ (a,b)|a,b\in S,a>b \right \}$, có $\left | K \right |=\binom{8}{2}=28$. Nếu $(a_1;b_1),(a_2;b_2),(a_3;b_3) \in K$ thoả mãn $a_1-b_1=a_2-b_2=a_3-b_3$ thì dễ chỉ ra $2$ tập con của $S$ thoả mãn.Gọi $C=\left \{ a-b|(a,b)\in K \right \}$, $t$ là số giá trị $d$ nằm trong tập $C$ mà tồn tại đúng $2$ phần tử $(a_1,b_1),(a_2,b_2)\in K$ thoả mãn $d=a_1-b_1=a_2-b_2$(do $S$ không thoả mãn đề bài nên $a_1=b_2$ hoặc $a_2=b_1$) . $C\subset \left \{ 1;2;...;23 \right \}$ nên $\left | K \right |-t\leq 23\Rightarrow t\geq 5$. $s\in S$ là $1$ số đặc biệt nếu tồn tại $(a,b)\in K$ sao cho $(a,s,b)$ là CSC. Nếu có $2$ phần tử $(a_1,b_1),(a_2,b_2)\in K$ để $(a_1,s,b_1),(a_2,s,b_2)$ là CSC thì $2$ tập con thoả mãn đề bài $(a_1,b_2),(a_2,b_1)$ (vô lí). Vì $t\geq 5$ nên số số đặc biệt ít nhất là $5$. Mặt khác số lớn nhất và nhỏ nhất trong $S$ không thể là số đặc biệt nên số số đặc biệt nhiều nhất là $6$. Lưu ý rằng khi $t=5$ thì $\left | C \right |\geq 28-5=23$ nên $C$ chứa tất cả các số từ $1$ đến $23$, $t=6$ thì $C$ không chứa nhiều nhất $1$ số trong tập từ $1$ đến $23$.

Số số đặc biệt là $5$, lúc đó có $23\in C$ nên $24,1\in S$. $22\in C$ nên $2$ hoặc $23$ thuộc $S$. Do tính đối xứng nên có thể giả sử $2\in S$, lúc đó $23$ không thuộc $S$. Nếu $3\notin S$ thì $2$ là số không đặc biệt duy nhất. $21\in C$ nên $22\in S$. $22$ là số đặc biệt nên $20\in S$. Lại có $18,21\notin S$ nên để $22$ là số đặc biệt thì $16\in S$. Dễ thấy $19,20\notin S$ và $16$ là số đặc biệt nên $10$ hoặc $8$ thuộc $S$. Trong cả $2$ trường hợp thì không thể chọn được số cuối cùng thuộc $S$. Nếu $3\in S$, $5\in S$, các phần tử của $S$ là $1<2<3<5<x_1<x_2<x_3<24$, $x_1-5$ khác $1$,$2$, $x_3-x_2,x_4-x_3,24-x_3$ đều lớn hơn $4$ nên $24=24-x_3+x_3-x_2+x_2-x_1+x_1-5+5\geq 5+3+5+5+6=24$. Dấu $"="$ xảy ra khi $x_1=8$; $x_2-8=x_3-x_2=5$,$24-x_3=6$ hoặc $24-x_3=x_3-x_2=5$, $x_2-8=6$. Cả $2$ trường hợp đều không thoả mãn. Vậy $3$ là số không đặc biệt duy nhất, tiếp tục lập luận suy ra điều vô lí

Số số đặc biệt là $6$. $22$ hoặc $23$ thuộc $C$ nên $24$ hoặc $23$ thuộc $S$. Nếu $24\notin S$ thì $23$ là số duy nhất không thuộc $C$. Có $1\in S$ và $21\in C$ nên theo tính đối xứng, giả sử $2\in S$.$2$ là số đặc biệt nên $3\in S$. $3$ cũng là số đặc biệt nên $5\in S$. Lập luận tương tự trường hợp trên suy ra điều vô lí. Vậy $1,24\in S$, nếu $22\in C$ thì theo tính đối xứng, giả sử $2\in S$, lập luận tương tự suy ra điều vô lí. Vậy $22$ là số duy nhất không thuộc $C$. $21\in C$ nên theo tính đối xứng, giả sử $3\in S$. $3$ là số đặc biệt nên $5\in S$. Vì $20\in C$ nên $23$ hoặc $21$ thuộc $S$. Nếu $23,24\in S$, lập luận tương tự trường hợp $1,2\in S$ suy ra điều vô lí. Vậy $21\in S$, dễ thấy $22,23\notin S$ và $21$ là số đặc biệt nên $18\in S$. $4\notin S$ và $5$ là số đặc biệt nên $9\in S$. Lúc này cặp $(9,18),(24,3)$ không thoả mãn.

Tóm lại giả sử sai, vậy $k=8$ là số tốt


Bài viết đã được chỉnh sửa nội dung bởi JUV: 02-12-2016 - 20:22





2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh