Chủ đề này có 3 trả lời

[supermember]

   Xin lỗi mọi người vì sự chậm trễ

 

 Bài 2:

 

Có $200$ người tham gia một kì thi giải toán.Trong đề có $6$ bài Toán.

 

Mỗi bài Toán bất kỳ trong đề đều có ít nhất $120$ người giải được.

 

Chứng minh rằng tồn tại $2$ thí sinh mà bất kỳ bài Toán nào trong đề đều được giải bởi $1$ trong $2$ người họ .

[Sagittarius912]

   Xin lỗi mọi người vì sự chậm trễ

 

 Bài 2:

 

Có $200$ người tham gia một kì thi giải toán.Trong đề có $6$ bài Toán.

 

Mỗi bài Toán bất kỳ trong đề đều có ít nhất $120$ người giải được.

 

Chứng minh rằng tồn tại $2$ thí sinh mà bất kỳ bài Toán nào trong đề đều được giải bởi $1$ trong $2$ người họ .

Giả sử, không có 2 thí sinh nào mà bất kì bài toán nào  trong đề được giải bởi 1 trong 2 họ

Ta kẻ bảng sau

Trong đó, mõi cột dọc tương ứng với mỗi thí sinh

6 hàng ngang tương ứng với 6 bài toán

Số "1" biểu thị là bài toán được giải quyết 

Số "0" biểu thị bài toán không được giải quyết 

Bây giờ ta sẽ đếm số cặp $\left ( 0;0 \right )$ trên bảng:

Theo như giả sử thì số số 0 nhiều nhất trên mỗi hàng ngang là $200-120=80$

Nên số cặp  $\left ( 0;0 \right )$ nhiều nhất trên bảng:

$n_{max} = 6.C_{80}^2$

Mặt khác số cặp  $\left ( 0;0 \right )$  trên toàn bảng là  $C_{200}^2$

Do đó để giả sử của chúng ta đúng thì 

 

$6.C_{80}^2 \ge C_{200}^2$  (vô lí)

 

$\Rightarrow$ điều giả sử sai

 

$\Rightarrow$ dpcm

Bài viết đã được chỉnh sửa nội dung bởi Sagittarius912: 22-03-2013 - 01:10

[cobk54]

Xem bit 0, 1 lần lượt là em học sinh không giải, giải được bài toán. Ta lập 1 ô vuông kích thước 6 x 200, và xếp gọn gàng các bit lên mỗi ô. Dễ thấy sẽ phải tồn tại ít nhất 1 hàng có 4 bit 1 (nếu có 5 hoặc 6 bit 1 thì bài toán được chứng minh luôn, còn nếu có không quá 3 bit 1 thì số bit 1 tổng cộng sẽ nhỏ hơn 600 < 720 (tiêu chuẩn của đề bài)). Xét hàng a có 4 bit 1, đương nhiên sẽ có 2 bit 0 trên hàng a. Trên cột chứa bit 0 đầu tiên sẽ có 120 bit 1, với mỗi hàng chứa bit 1 đó thì tại vị trí của cột chứa bit o của hàng a nếu tất cả đều là 0, sẽ dẫn mâu thuẫn vì chứa quá 121 bit 0. Mâu thuẫn dẫn tới bài toán được chứng minh, hihi.

Bài viết đã được chỉnh sửa nội dung bởi cobk54: 28-03-2013 - 17:15

[nhungvienkimcuong]

Em vẫn chờ các bài tiếp theo trong chùm bài này của anh  . Sau đây là một bài vừa mới thi gần đây sử dụng phương pháp này.

 

Bài toán. Tô tất cả các cạnh và đường chéo của một đa giác lồi $P$ có $43$ đỉnh bởi hai màu xanh hoặc đỏ. Biết rằng mỗi đỉnh đều là điểm kết thúc của $20$ đoạn đỏ và $22$ đoạn xanh. Một tam giác tạo bởi các đỉnh của $P$ được gọi là đơn sắc xanh (đỏ) nếu cả ba cạnh cùng chung màu xanh (đỏ). Giả sử có $2022$ tam giác đơn sắc xanh, hỏi có bao nhiêu tam giác đơn sắc đỏ?

(Bài 5 - IMC 2022)