Xin giới thiệu lời giải và bình luận đề Toán tuyển chọn đội tuyển VN dự IMO 2019 (hay gọi là đề Toán Vietnam TST 2019) của nhóm tác giả Trần...
Xin giới thiệu lời giải và bình luận đề Toán tuyển chọn đội tuyển VN dự IMO 2019 (hay gọi là đề Toán Vietnam TST 2019) của nhóm tác giả Trần Nam Dũng – Võ Quốc Bá Cẩn – Trần Quang Hùng.
Đề Toán Vietnam TST 2019 gồm 6 câu, mỗi câu 7 điểm. Tổng thời gian làm bài là 9 tiếng đồng hồ (trong 2 ngày). Xem chi tiết đề thi và lời giải trong 12 ảnh dưới đây.
Bình luận. Đây là một bài toán cực trị tổ hợp khá đơn giản. Ta có thể sử dụng ngôn ngữ đồ thị để trình bày lời giải gọn gàng và súc tích hơn. Khi đó thuật ngữ kết nối sẽ thành liên thông, bổ đề sẽ được phát biểu là một đồ thị khung liên thông n đỉnh có ít nhất n-1 cạnh.
Ngoài cách xây dựng ví dụ bằng thuật toán như ở trên, chúng ta còn có thể có những cách xây
dựng khác, chẳng hạn phân đồ thị đầy đủ Kn thành đường đi Hamilton (cách này khá khó, đặc biệt là trường hợp n chẵn). Bài toán này lúc đó sẽ có một cách phát biểu khác khá thú vị như sau: Có 2k người thuê 2k phòng đánh số từ 1 đến 2k: Sau mỗi một đêm họ lại đổi phòng sao cho hai người bất kỳ cạnh phòng nhau không quá một lần. Chứng minh rằng có cách sắp xếp để họ ở được k đêm.
Bình luận. Đây là một bài toán khá kỹ thuật. Ý tưởng sử dụng bộ lệnh để mô tả các bước đi của con bọ là khá tự nhiên, tuy nhiên bước chứng minh các bộ lệnh khác nhau (ở dạng rút gọn) dẫn đến các điểm khác nhau là không đơn giản. Nếu ta giới hạn trong các bộ lệnh gồm n lệnh thì cũng có thể chứng minh được, nhưng khó và quan trọng là tiếp theo vẫn chưa áp dụng được (vì có thể trùng với kết quả của các bộ lệnh ngắn hơn).
Bài này rõ ràng liên quan đến hệ nhị phân, do đó cũng có hướng giải sử dụng cách viết nhị nhân của số thực.
Cụ thể có thể đặt y=x/2 và sử dụng cách viết nhị phân. Như thế ta bắt đầu từ số 0; 1 và có hai phép toán: +1 và chia 2 (dịch dấu phẩy sang phải). Tuy nhiên, đó không phải là điểm mấu chốt. Lời giải trên đây không cần chuyển về hệ nhị phân nhưng có dùng đến tính duy nhất của khai triển nhị phân.
Đề Toán Vietnam TST 2019 gồm 6 câu, mỗi câu 7 điểm. Tổng thời gian làm bài là 9 tiếng đồng hồ (trong 2 ngày). Xem chi tiết đề thi và lời giải trong 12 ảnh dưới đây.
Ngoài cách xây dựng ví dụ bằng thuật toán như ở trên, chúng ta còn có thể có những cách xây
dựng khác, chẳng hạn phân đồ thị đầy đủ Kn thành đường đi Hamilton (cách này khá khó, đặc biệt là trường hợp n chẵn). Bài toán này lúc đó sẽ có một cách phát biểu khác khá thú vị như sau: Có 2k người thuê 2k phòng đánh số từ 1 đến 2k: Sau mỗi một đêm họ lại đổi phòng sao cho hai người bất kỳ cạnh phòng nhau không quá một lần. Chứng minh rằng có cách sắp xếp để họ ở được k đêm.
Bài này rõ ràng liên quan đến hệ nhị phân, do đó cũng có hướng giải sử dụng cách viết nhị nhân của số thực.
Cụ thể có thể đặt y=x/2 và sử dụng cách viết nhị phân. Như thế ta bắt đầu từ số 0; 1 và có hai phép toán: +1 và chia 2 (dịch dấu phẩy sang phải). Tuy nhiên, đó không phải là điểm mấu chốt. Lời giải trên đây không cần chuyển về hệ nhị phân nhưng có dùng đến tính duy nhất của khai triển nhị phân.
