(BMO 2009/10, vòng 2, bài toán số 1) Có $2010^{2010}$ đứa trẻ trong một trại hè. Mỗi người có nhiều nhất là $3$ người bạn trong trại hè, và tất nhiên, nếu $A$ là bạn của $B$ thì $B$ cũng là bạn của $A$. Trưởng trại muốn xếp các đứa trẻ này thành một hàng, sao cho có nhiều nhất $2010$ đứa trẻ giữa bất kì cặp gồm hai người bạn nào. Liệu có thể luôn luôn thực hiện được điều này hay không?
#2
Đã gửi 23-06-2016 - 07:03
Karl Heinrich Marx
-
- Thành viên
-
- 321 Bài viết
Sĩ quan
Ta sẽ chứng minh là không phải luôn luôn sắp được như vậy. Ta thiết kế một mối quan hệ giữa các đứa trẻ chỉ ra nó không thỏa mãn. Đầu tiên xét một đồ thị hình cây với đỉnh là một đứa trẻ (bậc 0). Đứa trẻ này có 3 người quen (bậc 1), 3 đứa này mỗi đứa lại quen 3 đứa khác nữa (bậc 2),.... cứ vậy mỗi đứa trẻ xuất hiện trong đồ thị lại quen với 3 đứa trẻ khác. Ta thành lập được một cây tam phân $n$ bậc, ta có thể cho $n=2010$ cũng được.
Giả sử tồn tại cách sắp xếp để thỏa mãn đk đề bài với những đứa trẻ thuộc cái cây này.
Xét vị trí của đứa trẻ ở đỉnh bậc 0 là $a$. Lấy vị trí của mỗi đứa trẻ trừ cho $a$, ta xem như vị trí của đứa trẻ ở bậc 0 là 0. Khi đó ta có thể chứng minh quy nạp theo $k$ là nếu một đứa trẻ thuộc cây tam phân ở bậc không vượt quá $k$ thì trị tuyệt đối vị trí của nó không vượt quá $2011k$.
Tuy nhiên tổng số đứa trẻ thuộc cây tam phân mà có bậc không vượt quá $k$ là $\frac{3^{k+1}+1}{2}$.
Ta chọn được $k$ đủ lớn mà bé hơn $2010$ để $\frac{3^{k+1}+1}{2}>2.2011k+1$.
Điều này chứng tỏ phải có 2 em trùng vị trí, vô lí.
Có thể tối ưu số em bé là $\frac{3^{k+1}+1}{2}$ với $k$ thỏa mãn bđt trên.
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh
