A problem which someone posted in Google's internal GooglePlus page (yeah...).
Show that there is a subset $S$ of $\{1, 2, \dots, 3^k - 1\}$ such that, $S$ has at least $2^k$ 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, \dots, 3^k - 1\}$ such that, $S$ has at least $2^k$ 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