Bình luận cho toàn bộ TST 2017 sẽ được đăng trên Sputnik Newsletter số 4 (04/2017), mời các bạn đón đọc!
(Nguyễn Tiến Dũng)
Các thầy Trần Nam Dũng và Ngô Văn Minh có nhờ tôi bình luận về bài toán số 1 của cuộc thi chọn đội tuyển IMO2017 của Việt Nam. Đề bài như sau:
Bài 1. Cho 44 cái lỗ phân biệt trên một cái rãnh là đường thẳng và 2017 con kiến. Mỗi con kiến sẽ chui lên từ một cái lỗ và bò đến một cái lỗ khác với vận tốc không đổi rồi chui xuống đó. Gọi T là tập các thời điểm mà con kiến chui lên hoặc chui xuống các cái lỗ. Biết rằng vận tốc của các con kiến đôi một khác nhau và |T| ≤ 45. Chứng minh rằng tồn tại ít nhất hai con kiến nào đó không gặp nhau.
Gợi ý lời giải: Có gì liên quan giữa các số 44, 45 và 2017? Dễ thấy 
Vậy tai sao lại dùng tích? Bởi vì có nhiều nhất là từng đó điểm (vị trí, thời gian chạm lỗ khi lên hoặc xuống lỗ) trên mặt phẳng toạ độ. Ta vẽ trên mặt phẳng toạ độ các đồ thị đường đi của các con kiến, mỗi đồ thị là 1 đoạn thẳng nối 2 trong số các điểm trên. Tất cả các đoạn thẳng đó đều có hướng khác nhau (vì vận tốc các con kiến khác nhau). Hướng ở đây hiểu là góc so với đường nằm ngang modulo pi.
Câu hỏi đặt ra bây giờ là nếu hai đoạn một đều có điểm chung (hai con kiến nào cũng có gặp nhau) thì có nhiều nhất là bao nhiêu đoạn thẳng?
Ta có thể sắp xếp thứ tự các đoạn thẳng theo thứ tự vòng tròn theo góc của chúng.
Cố định 1 đoạn đầu tiên, từ điểm A1 đến điểm A2. Đoạn thứ hai có hướng quay về “bên phải” so với đoạn thứ nhất, nên phải có thêm ít nhất 1 điểm mới A3 (tức là hoặc là A1A3 với A3 nằm bên phải A1A2, hoặc A3A2 với A3 nằm bên trái A1A2, hoặc A3A4 (hai điểm mới) nằm ở hai bên của A1A2). Thêm đoạn thứ 3 phải thêm ít nhất 1 điểm mới, trừ trường hợp tạo thành 3 đoạn A1A2, A1A3, A2A3. Cứ như thế: thêm 1 đoạn thì cần thêm ít nhất 1 điểm mới, trừ khi thêm đoạn cuối cùng thì dùng được 2 điểm cũ. Như vậy để có n đoạn đôi một có điểm chung thì cần ít nhất n điểm. Với n = 44 lần 45 thì có nhiều nhất là từng đó con kiến đôi một có gặp nhau. Vì 2017 lớn hơn 44 lần 45 nên có hai con kiến không gặp nhau.
Thay vì nói đến hướng modulo pi, có thể chứng minh bằng quy nạp kiểu khác cho dễ hình dung hơn: Ta sẽ chứng minh bằng quy nạp rằng nếu có n điểm trên mặt phẳng thì không tạo được quá n đoạn thẳng với các đỉnh là các điểm đó sao cho đôi một có điểm chung và không có hai đoạn nào song song hay đè lên nhau.
Với n = 2, 3: hiển nhiên
Từ n-1 đến n:
Nếu có 1 điểm với không quá 1 đoạn xuất phát từ điểm đó, thì xoá điểm đó (và đoạn đó) đi, đưa về trường hợp n-1 điểm.
Giả sử bây giờ đỉnh nào cũng có ít nhất 2 đoạn xuất phát. Nếu có đỉnh A có 3 đoạn xuất phát thì sẽ “có vấn đề”: chẳng hạn là AB, AC, AD. Nếu BCD chứa A bên trong thì đoạn thứ hai từ B không thể cùng cắt AC và AD. Nếu BCD không chứa A bên trong thì ta có chẳng hạn tia AC nằm giữa hai tia AB và AD. Khi đó đoạn thứ hai từ đỉnh C không thể cùng cắt AB và AD. Như vậy từ mỗi đỉnh chỉ có đúng 2 đoạn, suy ra số đoạn bằng đúng số đỉnh trong trường hợp này.