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

[Pirates]

1. Trong 1 giải cờ tướng có $2n$ người ($n > 1$) tham gia, biết rằng hai người bất kì đấu với nhau không quá 1 ván. Chứng minh rằng với các điều kiện đó không có 3 người nào chơi với nhau 3 ván, có thể được tổ chức trong và chỉ trong trường hợp nếu số tất cả các ván cờ chơi trong giải không vượt quá $n^{2}$.

2. Trong mỗi ô của bảng có kích thước 5x5 đặt một đồng tiền. Người ta thực hiện phép toán như sau: Chọn bất kỳ hai đồng tiền và mỗi một trong chúng di chuyển trong các ô lân cận (Có cạnh chung với ô ban đầu). Có thể có hay không kết quả được sao cho tất cả 25 đồng tiền tại một ô cho trước.

Bài viết đã được chỉnh sửa nội dung bởi Pirates: 27-09-2009 - 09:34

[nhoccoi]

Sửa lại đề cho rõ ràng đi bạn!!!

[nhoccoi]

Bài 2 bạn tự nghĩ ra ah?
Xem lại hộ cái???

[Pirates]

Bài 2 bạn tự nghĩ ra ah?
Xem lại hộ cái???

Bài 2 là Vô địch Nam Tư 1986, và đề là như thế chứ không phải mình nghĩ ra. Mình đã sửa lại công thức bài 1 và giờ đề ko sai gì nữa.

[tanlsth]

Bài 1 chuyển về dạng đồ thị. Có $2n$ điểm, không tồn tại tam giác. Chứng minh có tối đa $n^2$ cạnh.

Chứng minh bằng qui nạp. Giả sử đúng tới $n-1$. Xét $2n$ điểm, chọn ra $2$ điểm $A,B$ được nối với nhau và gọi $2n-2$ điểm còn lại là tập $X$. Dễ thấy theo giả thiết qui nạp tập $X$ có tối đa $(n-1)^2$ cạnh.

Với mỗi điểm $Y$ thuộc $X$ thì ít nhất một trong $2$ cặp $YA,YB$ không được nối với nhau, suy ra các cặp có dạng $TA, TB$ với $T \in X$ có tối đa $2n-2$ cạnh được nối. Suy ra tổng số cạnh nối tối đa là $(n-1)^2+2n-2+1=n^2$ .Bài toán được chứng minh

Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 02-10-2009 - 17:18