A problem which someone posted in Google's internal GooglePlus page (yeah...).
Show that there is a subset S of {1,2,…,3k−1} such that, S has at least 2k elements and any three distinct elements x,y,z of S do not satisfy x+y=2z
(i.e. no number is the average of some other two numbers).
Show that there is a subset S of {1,2,…,3k−1} such that, S has at least 2k elements and any three distinct elements x,y,z of S do not satisfy x+y=2z
(i.e. no number is the average of some other two numbers).
[Spoiler alert]
ReplyDeleteInduction on k works. Suppose for k we have a subset P of S satisfying the condition. For k+1, use P'=P union {x+2*3^k: x\in P}. Clearly P' satisfies the condition too.
Looks right to me.
Delete