Mathematics question

Question

Let a1, a2, . . . , an be distinct positive integers and let M be a set of n − 1 positive integers not containing s = a1 +a2 +  +an. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths a1, a2, . . . , an in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

? · Accepted Answer

Use MI. The case n=1 is trivial.
Suppose the statement holds for n.
Consider n+1 distinct positive integers a1,...,a_(n+1), and a set M of n positive integers not containing s=a1+...+a_(n+1).
WLOG, let a_(n+1) be the largest integer among a1,...,a_(n+1), and let m be the largest integer in M. 
By induction hypothesis, the is some order of a1,...,an such that he grasshopper never lands on M&#92;{m}. Write this order as b1, b2, ..., bn.
If for this order b1,...,bn, the grasshopper does not land on m either, then we can add a_(n+1) as the last step. Then the grasshopper will not land on M either because s in not in M.
If the grasshopper lands on m on some step bk, we can consider the order
b1,...,b_(k-1), a_(n+1), bk,...,bn
The grasshopper does not land on M on the first k-1 steps by our choice of the order b1,...,bn. 
Then on the step a_(n+1), because a_(n+1) is the largest of the n+1 integers and b1+...+bk=m, we have
b1+...+b-(k-1)+a_(n+1)>m.
Hence the grasshopper does not land on m at the step a_(n+1). But because m is the largest element of M, the grasshopper in fact does not land on any element of M at the step a_(n+1) and all following steps bk,...,bn. Hence we are done.

STEVIE-G™ · Answer

點解呢題IMO咁深既??>

匿名 · Answer

健康瘦身，開心美麗！

一杯營養相當於33種蔬菜, 6種水果, 內含多種營養素，蛋白素相等於5錢燕窩、2份蔬菜、1份水果、1塊牛扒同半杯鮮奶！

隨您喜歡轉味道，可加生果如蜜瓜、香蕉、奇異果做奶昔，鐘意飲牛奶、豆漿亦可加入改變口味，更有營養對美容暗瘡好好。

濃縮蘆薈汁
功能 :
促進體內自我潔淨功能令，消化系統更健康
紓緩消化系統壓力
維護消化系統功能正常運作，確保腸胃潔淨
清除體內毒素
增強免疫功能
對抗炎症消炎止痛
促進傷口愈合

我做文職133磅減22磅，改善頭痛、胃痛、暈車浪、靜脈曲脹

個女15歲三個月減20磅，改善鼻敏感，流鼻血，讀書仲拿第一添

健康新文化www.HealthComeTrue.com/life

Mathematics question

3 個解答