Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

TOPIC tổng hợp các bài toán tổ hợp rời rạc xuất phát từ các kì thi MO,các tạp chí các nước


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

#1 ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Quảng Trị
  • Sở thích:ANIME IS LOVE,ANIME IS LIFE

Đã gửi 22-06-2015 - 17:27

Tiếp nối thành công của Topic BĐT, mình xin mở Topic về Tổ hợp rời rạc từ kì thi các nước, lần này mình mở rộng ra thêm các tạp chí như THTT,Crux,... để thêm phần phong phú. Trước khi bắt đầu,mình có 1 số điều nhắc nhở:

-Tuân thủ các quy định của diễn đàn 

- Khi Post bài thì ghi Bài ... (xuất phát từ kì thi MO nào,tạp chí nào,...): Đề bài

Ví dụ:Bài X ( VMO  2011 ):

- Nếu bài đăng quá 3 ngày mà không có lời giải hoàn chỉnh nào thì chủ bài viết đăng lời giải cùng phân tích của mình bên cạnh lời giải đó

Mình sẽ cố gắng đăng cả những bài toán ở mức độ THCS để các bạn THCS có thể tham gia nhiệt tình

Mình xin bắt đầu với bài toán sau:

Bài 1 ( Romani ):

Cho số nguyên dương $n$. Có bao nhiêu số tự nhiên chia hết cho $3$, có $n$ chữ số và các chữ số đều thuộc $\left \{ 3,4,5,6 \right \}$

 


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#2 ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Quảng Trị
  • Sở thích:ANIME IS LOVE,ANIME IS LIFE

Đã gửi 22-06-2015 - 17:31

Bài 2 ( Thụy Sĩ 2006 ): 

Tính số tập con $X=\left \{ 1,2,...,2n \right \}$ sao cho không tồn tại $2$ phần tử có tổng bằng $2n+1$


Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 22-06-2015 - 17:31

FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#3 marcoreus101

marcoreus101

    Thượng sĩ

  • Thành viên
  • 235 Bài viết
  • Giới tính:Nam
  • Đến từ:United Kingdom
  • Sở thích:Ngủ

Đã gửi 22-06-2015 - 17:53

Bài 1 ( Romani ):

Cho số nguyên dương $n$. Có bao nhiêu số tự nhiên chia hết cho $3$, có $n$ chữ số và các chữ số đều thuộc $\left \{ 3,4,5,6 \right \}$

Xét hệ đếm cơ số 4 gồm 4 chữ số là ${3;4;5;6}$ lần lượt có các giá trị là $0,1,2,3$ trong hệ đếm 

Giá trị của $33...3_{(4)}$ gồm n chữ số 3 trong hệ đếm đó bằng 0 trong hệ thập phân

Giá trị của $66..6_{(4)}$ gồm n chữ số 6 trong hệ đếm đó bằng $4^{n}-1$ trong hệ thập phân

Nên số số tự nhiên lập được là $\begin{bmatrix} \dfrac{4^n-1}{3} \end{bmatrix}-\begin{bmatrix} \dfrac{0}{3} \end{bmatrix}+1=\begin{bmatrix} \dfrac{4^n+2}{3} \end{bmatrix}$

Spoiler


Bài viết đã được chỉnh sửa nội dung bởi namcpnh: 30-06-2015 - 12:54


#4 marcoreus101

marcoreus101

    Thượng sĩ

  • Thành viên
  • 235 Bài viết
  • Giới tính:Nam
  • Đến từ:United Kingdom
  • Sở thích:Ngủ

Đã gửi 22-06-2015 - 18:15

Bài 3 (T9/415-THTT): Ta gọi một bộ số nguyên tố đẹp khi tích của các số nguyên tố này bằng 10 lần tổng của chúng. Hãy tìm tất cả các bộ số nguyên tố đẹp nói trên (Các số trong bộ số không nhất thiết phải phân biệt)

Spoiler


Bài viết đã được chỉnh sửa nội dung bởi marcoreus101: 22-06-2015 - 18:16


#5 nhungvienkimcuong

nhungvienkimcuong

    Sĩ quan

  • Thành viên
  • 463 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT Nguyễn Du-Daklak
  • Sở thích:đã từng có

Đã gửi 22-06-2015 - 18:31

Bài 1 ( Romani ):

Cho số nguyên dương $n$. Có bao nhiêu số tự nhiên chia hết cho $3$, có $n$ chữ số và các chữ số đều thuộc $\left \{ 3,4,5,6 \right \}$

bài toán này là một bài toán rất quen thuộc và là một trong những ví dụ đầu tiên của phương pháp  truy hồi trong tổ hợp

 

Gọi $A_n,B_n$ lần lượt là tập các số tự nhiên có $n$ chữ số $\vdots 3$ và $\not \vdots 3$ được lập từ các số $\left \{ 3,4,5,6 \right \}$

$\blacksquare$ Xét một phần tử của $A_n$ thì có $2$ cách tạo thành một phần tử của $A_{n+1}$ và $2$ cách tạo thành một phần tử của $B_{n+1}$

$\blacksquare$ Xét một phần tử của $B_n$ thì có $1$ cách tạo thành một phần tử của $A_{n+1}$ và $3$ cách tạo thành một phần tử của $B_{n+1}$

từ đó ta có $\left\{\begin{matrix} \left | A_{n+1} \right |=2\left |A_n \right |+\left | B_n \right |\\\left | B_{n+1} \right | =2\left |A_n \right |+3\left | B_n \right | \end{matrix}\right.$

$\Rightarrow \left | A_{n+2} \right |-5\left | A_{n+1} \right |+4\left |A_{n} \right |=0$

mặt khác dễ thấy $\left | A_1 \right |=2,\left | A_2 \right |=6\Rightarrow \left | A_n \right |=\frac{4^n+2}{3}$


Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 22-06-2015 - 19:04

Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra  ~O) 

Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em  :wub: 

Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh  :ukliam2: 


#6 ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Quảng Trị
  • Sở thích:ANIME IS LOVE,ANIME IS LIFE

Đã gửi 22-06-2015 - 20:21

Bài 4 ( IMO 2011):

Giả sử $n> 0$ là 1 số nguyên. Cho 1 cái cân dĩa và $n$ quả cân khối lượng lần lượt là $2^0,2^1,...,2^{n-1}$. Ta đặt lên mỗi cái cân một trong $n$ quả cân, lần lượt từng quả một,theo cách để đảm bào dĩa cân bên phải không bao giờ nặng hơn dĩa cân bên trái. Ở mỗi bước ta chọn một trong các quả cân chưa được đặt lên rồi đặt nó lên dĩa bên phải,hoặc dĩa bên trái,cho đến khi tất cả các quả cân đều được đặt lên dĩa, Hỏi có bao nhiêu cách để thực hiện việc đặt cân theo đúng mục đích đặt ra?


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#7 huonggiangcute

huonggiangcute

    Binh nhì

  • Thành viên
  • 15 Bài viết
  • Giới tính:Nữ
  • Đến từ:THPT Chuyên Hùng Vương

Đã gửi 22-06-2015 - 20:50

Bài 4 ( IMO 2011):

Giả sử $n> 0$ là 1 số nguyên. Cho 1 cái cân dĩa và $n$ quả cân khối lượng lần lượt là $2^0,2^1,...,2^{n-1}$. Ta đặt lên mỗi cái cân một trong $n$ quả cân, lần lượt từng quả một,theo cách để đảm bào dĩa cân bên phải không bao giờ nặng hơn dĩa cân bên trái. Ở mỗi bước ta chọn một trong các quả cân chưa được đặt lên rồi đặt nó lên dĩa bên phải,hoặc dĩa bên trái,cho đến khi tất cả các quả cân đều được đặt lên dĩa, Hỏi có bao nhiêu cách để thực hiện việc đặt cân theo đúng mục đích đặt ra?

 

Giả sử với $n$ nguyên ta sắp đc đống cân tmyc bài toán .
Kí hiệu $f(n)$ là cách sắp của $n$ quả 
Khi đó sắp các quả $2^1,2^2,...,2^{n-1}$ Số cách xếp là $f(n-1)$

Xếp quả thứ 1 ở vị trí bất kì có $1+2(n-1)=2n-1$ cách

Nên $f(n)=f(n-1)(2n-1)$ nên $f(n)=(2n-1).(2n-3)...5.3.1$


Bài viết đã được chỉnh sửa nội dung bởi huonggiangcute: 22-06-2015 - 21:05


#8 ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Quảng Trị
  • Sở thích:ANIME IS LOVE,ANIME IS LIFE

Đã gửi 22-06-2015 - 20:56

Giả sử với $n$ nguyên ta sắp đc đống cân tmyc bài toán .
Kí hiệu $f(n)$ là cách sắp của $n$ quả 
Khi đó sắp các quả $2^1,...,2^{n-1}$ là $f(n-1)$
Xếp quả thứ 1 ở vị trí bất kì có $1+2(n-1)=2n-1$ cách
Nên $f(n)=f(n-1)(2n-1)$ nên $f(n)=(2n-1)!$

Về ý tưởng thì cũng được nhưng rất tiếc kết quả sai rồi

Em sai ở bước cuối cùng truy hồi, $f(n)=(2n-1)(2n-3)...3.1$ và lập luận bài toán chưa chặt chẽ 


Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 22-06-2015 - 21:03

FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#9 ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Quảng Trị
  • Sở thích:ANIME IS LOVE,ANIME IS LIFE

Đã gửi 22-06-2015 - 21:25

Bài 5 ( Vô địch cộng hòa Czech 1998 ):

Cho $X$ là 1 tập hợp gồm $14$ số nguyên dương phân biệt. Chứng minh rằng có 1 số nguyên dương $k\leq 7$ và có 2 tập con $k$ phần tử:

$\left \{ a_1,a_2,...,a_k \right \}$,$\left \{ b_1,b_2,...,b_k \right \}$ rời nhau của $X$ sao cho $\left | (\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_k})-(\frac{1}{b_1}+\frac{1}{b_2}+...+\frac{1}{b_k}) \right |< \frac{1}{1000}$

Bài này THCS hoàn toàn có thể giải được


Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 22-06-2015 - 21:26

FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#10 huonggiangcute

huonggiangcute

    Binh nhì

  • Thành viên
  • 15 Bài viết
  • Giới tính:Nữ
  • Đến từ:THPT Chuyên Hùng Vương

Đã gửi 22-06-2015 - 21:51

Bài 5 ( Vô địch cộng hòa Czech 1998 ):

Cho $X$ là 1 tập hợp gồm $14$ số nguyên dương phân biệt. Chứng minh rằng có 1 số nguyên dương $k\leq 7$ và có 2 tập con $k$ phần tử:

$\left \{ a_1,a_2,...,a_k \right \}$,$\left \{ b_1,b_2,...,b_k \right \}$ rời nhau của $X$ sao cho $\left | (\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_k})-(\frac{1}{b_1}+\frac{1}{b_2}+...+\frac{1}{b_k}) \right |< \frac{1}{1000}$

Bài này THCS hoàn toàn có thể giải được

Xét $k=7$ .số tập con có 7 phần tử từ $X$ là $C_{14}^{7}=3432$
Tổng nghịch đảo của nó không quá $\sum_{i=1}^{7} \frac{1}{i}<3$

Xét 3000 nửa khoảng $(0;\frac{1}{1000}];(\frac{1}{1000};\frac{2}{1000}].......(\frac{2999}{3000};1]$
Theo nguyên lí Dirichle thì tồn tại 1 khoảng chứa 2 tập con và bỏ đi trùng nhau ta chọn được 2 bộ số thoả mãn ycbt .Do đò bài toán đúng với  $k\leq 7$ 
P/s: Kẹp Lỏng   :lol:
 


Bài viết đã được chỉnh sửa nội dung bởi huonggiangcute: 22-06-2015 - 21:53


#11 ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Quảng Trị
  • Sở thích:ANIME IS LOVE,ANIME IS LIFE

Đã gửi 22-06-2015 - 22:04

Bài 6 ( IMO shortlist 2003 ):

Gọi $f(k)$ là số các số nguyên $n$ thỏa mãn các điều kiện sau:

i) $0\leq n< 10^k$, nên $n$ có đúng $k$ chữ số,với các chữ số $0$ đứng đầu nếu cần.

ii) Các chữ số của $n$ có thể hoán vị thành một số chia hết cho $11$

Chứng minh: $f(2m)=10f(2m-1)$ với mọi số nguyên dương $m$


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#12 Belphegor Varia

Belphegor Varia

    Thượng sĩ

  • Thành viên
  • 227 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:Ninh Binh
  • Sở thích:Number theory , Geometry

Đã gửi 23-06-2015 - 08:35

Bài 7 ( Rumani 1978) :

Trong một buổi dạ hội tập trung các chàng trai và các cô gái . Biết rằng nếu chọn ra một nhóm bất kì các chàng trai thì số các cô gái quen với ít nhất $1$ chàng trai từ nhóm này sẽ không nhỏ hơn số chàng trai trong nhóm . Chứng minh rằng tất cả các chàng trai có thể cùng một lúc nhảy đôi với các cô gái mà mình quen 


$ \textbf{NMQ}$

Wait a minute, You have enough time. Also tomorrow will come 

Just take off her or give me a ride 

Give me one day or one hour or just one minute for a short word 

 


#13 ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Quảng Trị
  • Sở thích:ANIME IS LOVE,ANIME IS LIFE

Đã gửi 23-06-2015 - 14:50

Bài 8 ( Liên Xô 1965 ) :

Trong cuộc hội thảo có 40 cuộc họp, mỗi cuộc họp có 10 thành viên. Cho biết hai thành viên bất kì chỉ cùng dự họp với nhau tối đa một lần. Chứng minh rằng cuộc hội thảo có nhiều hơn 60 thành viên.


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#14 ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Quảng Trị
  • Sở thích:ANIME IS LOVE,ANIME IS LIFE

Đã gửi 23-06-2015 - 15:15

Có vẻ các mem vẫn còn khá e ngại phần tổ hợp nên mình sẽ giảm thời gian đăng lời giải xuống còn 1 ngày ( đối với mình ) và 2 ngày đối với các mem có đăng đề bài

Mình sẽ giải câu 2 trước:

Ta sẽ đi tính số tập con của tập $X$ sao cho không tồn tại 2 phần tử có tổng bằng $2n+1$Gọi số tập con đó là $a_n$. Xét tập $X_{n+1}=\left \{ 1,2,...,2n+2 \right \}$ có $a_{n+1}$ tập con tồn tại 2 phần tử có tổng bằng $2n+3$. Chia $a_{n+1}$ tập này thành 2 nhóm:

- Những tập không chứa hoặc chứa 1 trong 2 phần tử 1 và $2n+2$

Lúc này nhận thấy để những tập này chứa 2 phần tử sao cho tổng của chúng bằng $2n+3$ thì chúng phải chứa 2 phần tử trong tập hợp $\left \{ 2,3,...,2n+1 \right \}$ mà tổng bằng $2n+3$

Và mặt khác tồn tại 1 song ánh đi từ tập $\left \{ 2,3...,2n+1 \right \}$ vào $\left \{ 1,2,...,2n \right \}$ và số tập con của $\left \{ 2,3,...,2n+1 \right \}$ sao cho tồn tại 2 phần tử có tổng bằng $2n+3$ chính bằng $a_n$

Suy ra trong nhóm này, số các tập con chứa 1 bằng số các tập con chứa $2n+2$ bằng số các tập con không chứa 1 và $2n+2$ và bằng $a_n$

Vậy số tập cần tìm trong nhóm này là $3a_n$

- Những tập chứa cả 2 phần tử 1 và $2n+2$.

Lúc này do $1+2n+2=2n+3$ nên số tập con cần tìm chính là số tập con của tập $\left \{ 2,3,...,2n+1 \right \}$ và bằng $2^{2n}$. Vậy nên $a_{n+1}=a_n+4^n$

Từ đây ta tính được $a_n=4^n-3^n$

Vậy số tập thỏa mãn yêu cầu đề bài là $4^n-(4^n-3^n)=3^n$

 

Bình luận: Trong phương pháp đếm dựa vào quan hệ truy hồi. Khi xây dựng công thức truy hồi,ta có thể chia tập thành 2 nhóm có phần tử mới thỏa mãn đưa vào hoặc không để đưa về trường hợp trước


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#15 khanghaxuan

khanghaxuan

    Trung úy

  • Thành viên
  • 969 Bài viết
  • Giới tính:Nam
  • Sở thích:Bất đẳng thức , Tổ Hợp .

Đã gửi 23-06-2015 - 16:33

Bài 7 ( Rumani 1978) :

Trong một buổi dạ hội tập trung các chàng trai và các cô gái . Biết rằng nếu chọn ra một nhóm bất kì các chàng trai thì số các cô gái quen với ít nhất $1$ chàng trai từ nhóm này sẽ không nhỏ hơn số chàng trai trong nhóm . Chứng minh rằng tất cả các chàng trai có thể cùng một lúc nhảy đôi với các cô gái mà mình quen 

Bài 7 là một cách phát biểu khá dí dỏm của định lý Hall được phát biểu không kém phần hài hước như sau : 

Giả sử ta có một số chàng trai và một số cô gái được biểu diễn như sau : Ta biểu diễn các chàng trai bằng các chấm màu đỏ và các cô gái bằng các chấm màu xanh . Một điểm màu xanh được nối với một điểm màu đỏ nếu cô gái nằm trong tầm ngắm của chàng trai (Chú ý là không có hai đường nối nào giữa hai điểm cùng màu :P ) . Ta gọi là " amazing matching " nếu bất kì một chàng trai nào cũng có một ý trung nhân của mình . Định lý Hall phát biểu như sau : Với mọi tập đỏ gồm k điểm đỏ bất kì nếu ứng với tập điểm S đó luôn tồn tại số đỉnh xanh nối với tập S ít nhất là k thì " amazing matching " sẽ xảy ra tức là không một chàng trai nào ế vợ :P

Quay lại bài toán trên :  Ta để ý giả thiết : bất kì các chàng trai thì số các cô gái quen với ít nhất $1$ chàng trai từ nhóm này sẽ không nhỏ hơn số chàng trai trong nhóm do đó áp dụng định lý Hall ta được ĐPCM

Còn về chứng minh định lý Hall không khó :))

Định lý Hall còn dùng để chứng minh định lý Birkoff

Spoiler


Bài viết đã được chỉnh sửa nội dung bởi khanghaxuan: 23-06-2015 - 16:37

Điều tôi muốn biết trước tiên không phải là bạn đã thất bại ra sao mà là bạn đã chấp nhận nó như thế nào .

- A.Lincoln -

#16 khanghaxuan

khanghaxuan

    Trung úy

  • Thành viên
  • 969 Bài viết
  • Giới tính:Nam
  • Sở thích:Bất đẳng thức , Tổ Hợp .

Đã gửi 23-06-2015 - 16:49

Bài 4 ( IMO 2011):

Giả sử $n> 0$ là 1 số nguyên. Cho 1 cái cân dĩa và $n$ quả cân khối lượng lần lượt là $2^0,2^1,...,2^{n-1}$. Ta đặt lên mỗi cái cân một trong $n$ quả cân, lần lượt từng quả một,theo cách để đảm bào dĩa cân bên phải không bao giờ nặng hơn dĩa cân bên trái. Ở mỗi bước ta chọn một trong các quả cân chưa được đặt lên rồi đặt nó lên dĩa bên phải,hoặc dĩa bên trái,cho đến khi tất cả các quả cân đều được đặt lên dĩa, Hỏi có bao nhiêu cách để thực hiện việc đặt cân theo đúng mục đích đặt ra?

Giả quyết luôn cho nóng :P

Lời giải bài 4 : Dựa vào đề bài ta có thể suy ra được đĩa cân bên trái luôn nặng hơn đĩa cân phải ít nhất là 1 . Do đó tại một thời điểm nào đó ta có thể đặt quả cân 1 ở bất kì đĩa cân nào . 

Gọi $S(n)$ là số cách đặt thỏa mãn đề bài . 

Ta xét các đĩa cân $2,2^{2},...,2^{n-1}$ thì ta có $S(n-1)$ cách . 

Còn đĩa cân có cân nặng là 1 thi ta có 2 TH sau : 

- Nếu ta đặt đĩa cân này ở lượt đầu tiên thì ta chỉ có thể đặt ở đĩa bên trái nên ta có 1 cách

- Nếu đặt trong các lượt tiếp theo thì hiển nhiên ta cũng có thể đặt bên phải hay bên trái nên ta có $2(n-1)$

Nên ta có hệ thức truy hồi sau : $S(n)=(2n-1)S(n)$

Tới đây , các mem tự giải nhé :)) với chú ý $S(1)=1$


Bài viết đã được chỉnh sửa nội dung bởi khanghaxuan: 23-06-2015 - 16:49

Điều tôi muốn biết trước tiên không phải là bạn đã thất bại ra sao mà là bạn đã chấp nhận nó như thế nào .

- A.Lincoln -

#17 Belphegor Varia

Belphegor Varia

    Thượng sĩ

  • Thành viên
  • 227 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:Ninh Binh
  • Sở thích:Number theory , Geometry

Đã gửi 23-06-2015 - 17:14

Bài 7 ( Rumani 1978) :

Trong một buổi dạ hội tập trung các chàng trai và các cô gái . Biết rằng nếu chọn ra một nhóm bất kì các chàng trai thì số các cô gái quen với ít nhất $1$ chàng trai từ nhóm này sẽ không nhỏ hơn số chàng trai trong nhóm . Chứng minh rằng tất cả các chàng trai có thể cùng một lúc nhảy đôi với các cô gái mà mình quen 

Lời giải 2 theo mức độ THCS : 
Ta sẽ giải bài toán bằng quy nạp theo $n$ là số chàng trai . Với $n=1$ , khẳng định được chứng minh vì với mỗi chàng trai nhất định tìm được cô gái mà mình quen.
Giả sử khẳng định được chứng minh với số chàng trai nhỏ hơn $n$ . Ta sẽ chứng minh nó đúng với $n$ . Xét 2 trường hợp :

 

$\cdot$ Tìm được một nhóm $A$ từ $k<n$ chàng trai sao cho tổng số các cô gái quen với họ bằng $k$ . Giả sử mỗi chàng trai nhảy với $1$ cô gái mà mình quen (giả thiết quy nạp). Khi đó đối với số còn lại các chàng trai và các cô gái điều kiện bài toán được thực hiện . Thật vậy , nếu có nhóm B từ $i$ chàng trai không thuộc nhóm A, thì khi đó các chàng trai thuộc hợp của A và B sẽ không có ít hơn $i+k$ cô gái mà họ quen. Các chàng trai của nhóm A quen với không nhiều hơn $k$ cô gái,như vậy $i$ chàng trai nhóm B sẽ quen với ít nhất $i$ cô gái còn lại.Khi đó mỗi chàng trai  có thể nhảy với 1 cô gái họ quen .
 

$\cdot$ Ở một nhóm bất kỳ với $k$ bất kỳ $(k<n)$ các chàng trai có số các cô gái họ quen vượt quá $k$. Khi đó nếu trong các chàng trai nhảy với cô gái mình quen vượt quá $k$ thì tập hợp các chàng trai và các cô gái còn lại sẽ thỏa mãn điều kiện bài toán . Thật vậy, một nhóm bất kì $k<n$ chàng trai còn lại quen với không ít hơn $k+1$ cô gái, như vậy theo giả thiết quy nạp, mỗi chàng trai trong số còn lại cũng có thể nhảy với cô gái quen của mình   

 

Tóm lại tất cả các chàng trai có thể "quẩy " với các cô gái mà mình quen 


$ \textbf{NMQ}$

Wait a minute, You have enough time. Also tomorrow will come 

Just take off her or give me a ride 

Give me one day or one hour or just one minute for a short word 

 


#18 khanghaxuan

khanghaxuan

    Trung úy

  • Thành viên
  • 969 Bài viết
  • Giới tính:Nam
  • Sở thích:Bất đẳng thức , Tổ Hợp .

Đã gửi 23-06-2015 - 17:16

Bài 1 còn một lời giải khá hàn lâm bằng HÀM SINH như sau : 

Ta nói một chút qua ý tưởng đếm bằng hàm sinh như sau : Ta sẽ sử dụng một hàm đa thức để biểu diễn các trường hợp có thể xảy ra của đối tượng sau đó ta chỉ cần tìm hệ số của biến thỏa mãn đề bài . 

Ta gọi $a_{n}$ là tổng hệ số của $x^{3k}$ trong khai triển $F(x)=(x^{3}+x^{4}+x^{5}+x^{6})^{n}$

Ta có thể lập được một hàm như thế là vì : Cứ với mỗi số $n$ thì có thể có các chữ số 3 ,4,5,6 do đó để ẩn dụ cho các trường hợp đó thì ta kí hiệu $x^{3},x^{4},x^{5},x^{6}$ để tượng trưng

Vì đề bắt ta tìm tất cả các số chia hết cho $3$ nên ta sẽ tìm hệ số của số hạng $x^{3k}$

Vì cái mũ $n$ nên ta sẽ khó có thể xác định được hệ số cần tìm , tuy nhiên việc đó sẽ được dễ dàng hóa thông qua định lý sau : 

ĐỊNH LÝ RUF :  (Theo mình nhớ thì nó như thế này thì phải :closedeyes: )

Cho $n\in Z^{+}$ , đặt $\epsilon =cos \frac{2\pi}{n}+i.sin \frac{2\pi}{n}$ và tiếp theo ta xét đa thức :

$f(x)=a_{0}+a_{1}x+...+a_{n}x^{n}+...$ thì ta có : $a_{0}+a_{n}+a_{2n}+...=\frac{1}{n}(\sum_{i=1}^{n-1}f(\epsilon ^{i}))$

Áp dụng định lý RUF với $n=3$ (do ta cần tìm hệ số của các số hạng $x^{3k}$) 

Ta có : $a(n)=\frac{F(1)+F(\epsilon)+F(\epsilon ^{2})}{3}=\frac{4^{n}+2}{3}$

 

P/s : Nếu có gì sai trong khâu phân tích thì giúp nhé , chứ bỏ tổ lâu quá , quên gần hết :P


Bài viết đã được chỉnh sửa nội dung bởi khanghaxuan: 23-06-2015 - 17:29

Điều tôi muốn biết trước tiên không phải là bạn đã thất bại ra sao mà là bạn đã chấp nhận nó như thế nào .

- A.Lincoln -

#19 hxthanh

hxthanh

  • Thành viên
  • 3327 Bài viết
  • Giới tính:Nam

Đã gửi 23-06-2015 - 17:55

Bài 2 ( Thụy Sĩ 2006 ): 

Tính số tập con $X=\left \{ 1,2,...,2n \right \}$ sao cho không tồn tại $2$ phần tử có tổng bằng $2n+1$

Bài này có thể tính trực tiếp:

Chia $X$ thành $n$ nhóm $(1,2n);\;(2,2n-1);\;...;(n,n+1)$

Mỗi tập con gồm $k$ phần tử của $X$ thỏa yêu cầu đề bài phải được lấy từ $k$ cặp khác nhau. Có ${n\choose k}$ cách chọn $k$ cặp, mỗi cặp lại có $2$ cách chọn phần tử. Nên số tập con là:

$S=\sum_{k=0}^n {n\choose k}2^k=(1+2)^n$


Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!

#20 ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Quảng Trị
  • Sở thích:ANIME IS LOVE,ANIME IS LIFE

Đã gửi 23-06-2015 - 20:02

Bài 9 ( VMO ):

Cho tập $S=\left \{ 1,2,...,n \right \}$. Gọi $T$  là tập tất cả các tập con không rỗng của $S$. Với mỗi $X$ thuộc $T$, gọi $m(X)$ là trung bình cộng các phần tử của $X$. Tính $m=\frac{\sum m(X)}{\left | T \right |}$


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:




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

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