Finite Playground

To verify is human; to prove, divine.


2 Comments

IMO 2009 Q6

從 Terence Tao 陶哲軒的 blog “What’s New” 上看到的,
花了大約一個小時找對了解題的方向, 就沒有再做下去了,
設計的很精良的題目, 有興趣可以試試看!

A = \{a_1, \ldots, a_n\} 皆為相異正整數, 令 M = \{m_1, \ldots, m_{n-1}\} 為正整數, 但其中不包含 s = \sum_i a_i. 有一隻蚱蜢, 從數線原點開始往右跳 n 步, 步伐長正好是 A 的某種排序.

請證明聰明的蚱蜢可以找出一種 A 的排序使得牠跳的每一步都不會落在 M 中的任一點上.