Finite Playground

To verify is human; to prove, divine.

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 中的任一點上.


Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

2 thoughts on “IMO 2009 Q6

  1. hi, 我在 PTT Math 板有寫了一個證明, 可以參考看看XD

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s