Đế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

Bài tổ hợp BMO 2010


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

#1 IHateMath

IHateMath

    Thượng sĩ

  • Thành viên
  • 299 Bài viết
  • Giới tính:Không khai báo
  • Sở thích:Olympiad Math & Computer Sci

Đã gửi 08-06-2016 - 21:54

(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 Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

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

Đã gửi 23-06-2016 - 07:03

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.






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

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