Finite Playground

To verify is human; to prove, divine.

IMO 2009 Q6

2 Comments

從 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:

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