Giải bài 6 IMO 2009

Bài 6 trong kỳ thi Vô địch toán quốc tế 2009 (tổ chức tại Đức) là một bài tổ hợp hết sức thú vị và cũng rất hại não.

Đề bài

Giả sử a1, a2, . . . , an là các số nguyên dương khác nhau từng cặp và M là tập hợp gồm n 1 số nguyên dương không chứa số s = a1 + a2 + · · · + an. Một con châu chấu nhảy dọc theo trục thực, xuất phát từ điểm 0 và tiến hành n bước nhảy về bên phải với độ dài các bước nhảy là a1, a2, . . . , an theo một thứ tự nào đó. Chứng minh rằng con châu chấu có thể chọn thứ tự các bước nhảy sao cho nó không bao giờ nhảy lên bất kỳ điểm nào thuộc M.

Ta sẽ chứng minh bằng quy nạp

Với n = 1, 2; tầm thường.

Giả sử bài toán đúng tới n = k (k >= 3), ta sẽ chứng minh nó cũng đúng với n = k + 1.

Đặt dãy P = {a[1], a[2], …, a[k+1]} và s = sum{P}.

Gọi a[i] = max{P} và m = max{M}. Xét mối tương quan giữa s – a[i] và m.

Nếu s – a[i] = m

0_______s-a[i]-a[j]______s-a[i] = m______s

Theo giả thiết quy nạp, đối với dãy {P \ a[i]} và tập {M \ m} ta tìm được một thứ tự Q thỏa mãn cho châu chấu. Giả sử Q kết thúc với bước nhảy dài a[j], do a[j] < a[i] nên ta đổi chỗ a[j] với a[i] thì châu chấu sẽ vượt qua m và đây là thứ tự cần tìm cho dãy P và tập M.

Nếu s – a[i] > m

0________m_______s-a[i]______s

Dĩ nhiên s-a[i] sẽ ko thuộc M do m = max{M}. Theo giả thiết quy nạp, đối với dãy {P \ a[i]} và tập {M \ m} ta tìm được một thứ tự Q thỏa mãn cho châu chấu. Có 2 trường hợp xảy ra:

  • Nếu Q ko đi qua m thì Q rồi a[i] là thứ tự cần tìm cho dãy P và tập M.
  • Nếu Q đi qua m ở bước nhảy a[j], ta đổi chỗ a[j] với a[i] và đây là thứ tự cần tìm cho dãy P và tập M.

Nếu s – a[i] < m

0______s-a[i]_____m______s

Có 2 trường hợp xảy ra:

Nếu s-a[i] ko thuộc M

Theo giả thiết quy nạp, đối với dãy {P \ a[i]} và tập {M \ m} ta tìm được một thứ tự Q thỏa mãn cho châu chấu. Khi đó Q rồi a[i] là thứ tự cần tìm cho dãy P và tập M.

Nếu s-a[i] thuộc M

Xét k cặp số bao gồm k*2 số khác nhau hoàn toàn: (s-a[j], s-a[i]-a[j]) trong đó a[j] thuộc {P \ a[i]}. Nếu cặp nào cũng tồn tại ít nhất một số thuộc M thì ta có ít nhất k số khác nhau thuộc M, kể thêm s-a[i] và m thì hóa ra M có tới ít nhất k+2 phần tử, vô lý vì M chỉ có k+1 phần tử.

Vậy tồn tại cặp (s-a[t], s-a[i]-a[t]) đều ko thuộc M, như sơ đồ sau:

0_____s-a[i]-a[t]____s-a[i]___m___s-a[t]____s

Theo giả thiết quy nạp, đối với dãy {P \ a[i] \ a[t]} và tập {M \ m \ s-a[i]} ta tìm được một thứ tự Q thỏa mãn cho châu chấu. Khi đó Q rồi a[i] rồi a[t] là thứ tự cần tìm cho dãy P và tập M.

Vậy trong tất cả các trường hợp ta đều có đpcm và giả thiết quy nạp là đúng với mọi n.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s