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

[kimcuong]

Trong cuốn tìm tòi và sáng ạo của HS chuyên toán-tin trường tự nhiên có bài (ko giải đáp)
Cho một bảng ô vuông vô tận, mỗi ô ta điền một số nguyên dương. CMR: ta luôn tìm được 1 hình chữ nhật mà bốn ô ở bốn góc của hình chữ nhật này là các sô nguyên dương có hai chữ số tận cùng giống nhau.


Bài 2: (đề thi khảo sát môn chuyên lớp 10 toán chuyên vĩnh Phúc)
Trong một hội nghị có 1999 người tham dự. Biết cứ 50 người bất kì luôn có 2 ngưòi ko quen biết nhau. CMR: ta luôn tìm đựơc 41 ngưòi sao cho mỗi ngưòi trong số họ quen ko quá 1958 ngưòi khác trong hôi nghị.

[nhoccoi]

Bài 2:
Giả sử chỉ tìm được nhiều nhất 40 người, mỗi người quen nhiều nhất 1958 người khác:
Nghĩa là có ít nhất 1959 người, mỗi người quen ít nhât 1959 người khác
Khi đó, ta sẽ chỉ ra tồn tại 50 người trong 1959 người này đôi 1 quen biết nhau:
+) Xét 2 người bất kì, có ít nhất 1959*2- 1999 người quen chung
+) Xét 3 người, trong đó gồm 2 người nói trên và 1 người quen chung của 2 người đó, 3 người này có ít nhất 1959*2- 1999+ 1959_ 1999=1959* 3- 2*1999
......................
+)Xét như trên đến 49 người, có it nhất 1959* 49- 1999* 48= 39 người quen chung
Chọn bất kì 1 trong 39 người trên ta được 50 người đôi 1 quen biết nhau
=>mâu thuẫn

[kimcuong]

Bài 2:
Giả sử chỉ tìm được nhiều nhất 40 người, mỗi người quen nhiều nhất 1958 người khác:
Nghĩa là có ít nhất 1959 người, mỗi người quen ít nhât 1959 người khác
Khi đó, ta sẽ chỉ ra tồn tại 50 người trong 1959 người này đôi 1 quen biết nhau:
+) Xét 2 người bất kì, có ít nhất 1959*2- 1999 người quen chung
+) Xét 3 người, trong đó gồm 2 người nói trên và 1 người quen chung của 2 người đó, 3 người này có ít nhất 1959*2- 1999+ 1959_ 1999=1959* 3- 2*1999
......................
+)Xét như trên đến 49 người, có it nhất 1959* 49- 1999* 48= 39 người quen chung
Chọn bất kì 1 trong 39 người trên ta được 50 người đôi 1 quen biết nhau
=>mâu thuẫn

Sao con số 39 to thế nhỉ?
Bài 1 là đề thi chọn đội tuyển trường sư phạm năm 2000-2001! Viết nhầm!

[nhoccoi]

Con số to vì họ lấy năm 1999!
không nhớ rõ lắm là thi gì.

[nhoccoi]

Bài 1:
Bài toán có thể đem về: mỗi ô ta điền 1 số nguyên dương tư 0->99.cần chứng minh tồn tại hình chữ nhật 4 đỉnh là 4 số giống nhau.
Giả sử không tồn tại.
Xét 1 hàng ngang bất kì luôn tồn tại 101 ô được điền bởi 1 số a
Xét hàng ngang song song với hang ngang nói trên và chỉ xét 101 số cùng cột với 101 số trên
=> mỗi hang luôn tồn tại 2 ô được đanh bởi 1 số ( vì 101=100+1) ( số này khác a)
Ta gọi hàng chứa 2 ô được đánh bởi số b là hàng b (
Xét tất cả C(2,101)* 99 +1 hàng:
Tồn tại C(2,101)+ 1 hàng k
Trong mỗi hàng có C(2,101) cách chọn vị trí cho 2 số k
=>tồn tại 2 hang mà vị trí của 2 số k giống nhau (thuộc 2 cột)
Khi đó 4 số k này sẽ tạo thành hcn
=> mâu thuẫn

[chuyentoan]

Có một cách như sau:

Xét hình chữ nhật có chiều ngang là $100^{101}$ và chiều dọc là $100$. Ta xét các điểm nguyên được điền số trong và trên biên của hình chữ nhật này. Xét các bộ $101$ số xếp liền nhau theo chiều dọc. Do các số chỉ có thể từ $00$ đến $99$ nên có tất cả $100^{101}$ bộ $101$ số như vậy. Mà có tất cả $100^{101}+1$ bộ dọc như thế. Theo nguyên tắc Dirichlet thì có hai bộ $101$ như thế giống hệt nhau. Trong mỗi hai cột dọc này do đều có $101$ số nên có $2$ số giống nhau, mà hai cột này giống nhau, suy ra có $4$ đỉnh của một hình chữ nhật được điền các số giống nhau!

[kimcuong]

Bài 2:
Giả sử chỉ tìm được nhiều nhất 40 người, mỗi người quen nhiều nhất 1958 người khác:
Nghĩa là có ít nhất 1959 người, mỗi người quen ít nhât 1959 người khác
Khi đó, ta sẽ chỉ ra tồn tại 50 người trong 1959 người này đôi 1 quen biết nhau:
+) Xét 2 người bất kì, có ít nhất 1959*2- 1999 người quen chung
+) Xét 3 người, trong đó gồm 2 người nói trên và 1 người quen chung của 2 người đó, 3 người này có ít nhất 1959*2- 1999+ 1959_ 1999=1959* 3- 2*1999
......................
+)Xét như trên đến 49 người, có it nhất 1959* 49- 1999* 48= 39 người quen chung
Chọn bất kì 1 trong 39 người trên ta được 50 người đôi 1 quen biết nhau
=>mâu thuẫn

XIN HỎI BẠN NÀY: Xét 3 nguời trong đó gồm 2 NGƯOIỪ NÓI TRÊN VÀ MỘT NGUỜI QUEN chung thế bạn xử lí chỗ cuối thế nào, chắc gì 48 nguời đã có 1 nguời quen chung???
Với bài 1 bạn làm rắc rối giữu! Cách của abnj chuyentoan dễ hiêẻ hon mà ngắn hơn nữa...
Dù sao thank bạn RẤT NHIỀU!!!!!!!!!!!!!!!!!

[nhoccoi]

Hai người tớ xét lúc đầu là quen nhau,người thứ 3 lại quen cả 2,người thứ tư quen cả 3....
vẽ đồ thị ra.quen nhau thì nối 2 điểm lại sẽ thấy ngay đôi một quen biết nhau!!!

[kimcuong]

Hai người tớ xét lúc đầu là quen nhau,người thứ 3 lại quen cả 2,người thứ tư quen cả 3....
vẽ đồ thị ra.quen nhau thì nối 2 điểm lại sẽ thấy ngay đôi một quen biết nhau!!!

Cậu ko hiểu ý tớ nói rồi. Tớ muốn biết đến sau khi chọn được 48 ngừời rồi nhá! Xét người thứ 49 là ngưìư quen chung của 48 người kia thế thì chắc gì đã tồn tại nguời thứ 49 như thế???

[nhoccoi]

theo nguyên lý dirichle thôi 2 nguời thì 1959*2-1999
3 người thì 1959*3-1999*2
48 người có người quen chung vì 1959*48-1999*47=79

[kimcuong]

theo nguyên lý dirichle thôi 2 nguời thì 1959*2-1999
3 người thì 1959*3-1999*2
48 người có người quen chung vì 1959*48-1999*47=79

Hôm nay chữa bài.Cách của anh giống hệ cách của thầy em! Mà anh xây dựng tập hợp A là nhũng người ko quen quá 1958 người khác. Như vậy số phần tử của A ko vượt quá 40 người theo giả sử của mình. Mỗi tập số giao nhau có hơn 40 phần tử => tồn tại người quen chung. Đến người thứ 50 thì ko cần xét A nữa.