Let $k$ be a positive integer. Prove that one can partition the set $\{ 0,1,2,3, \cdots ,2^{k+1}-1 \}$ into two disdinct subsets $\{ x_1,x_2, \cdots, x_{2k} \}$ and $\{ y_1, y_2, \cdots, y_{2k} \}$ such that $\sum_{i=1}^{2^k} x_i^m =\sum_{i=1}^{2^k} y_i^m$ for all $m \in \{ 1,2, \cdots, k \}$.
Problem
Source: China TST 2005
Tags: induction, combinatorics
N.T.TUAN
02.02.2007 05:37
I know one solution of this problem,
use Morse's sequence
see http://mathworld.wolfram.com/Thue-MorseSequence.html
or http://en.wikipedia.org/wiki/Thue-Morse_sequence
tmbtw
02.02.2007 11:33
N.T.TUAN wrote: I know one solution of this problem,
use Morse's sequence
see http://mathworld.wolfram.com/Thue-MorseSequence.html
or http://en.wikipedia.org/wiki/Thue-Morse_sequence
Lemma Set{$n+1;n+2;...;n+2^{k}$}can be patitioned into two sets A,B satisfying the question. proof Induction by k (Sorry-I'm very busy )
bilarev
10.03.2007 13:02
I have a question which doesn't seem to be trivial: How can we prove that the sets $S=\{1,2,...,2^{n}\},$ $S_{0}=\{n|n\in S, t_{n}=0\}$ and $S_{1}=\{n|n\in S, t_{n}=1\},$ where $\{t_{n}\}_{n=0}^{\infty}$ is the Thue-Morse sequence, have the property \[\sum_{x\in S_{0}}x^{s}=\sum_{y\in S_{1}}y^{s}\] for $s=0,1,...,n-1$ : Thanks
probability1.01
11.03.2007 01:31
Use strong induction. Notice that $\sum_{x \in S_{0}}x^{s}= \sum_{y \in S_{1}}y^{s}$ $\iff \sum_{x \in S_{0}, x \le 2^{n-1}}x^{s}-(x+2^{n-1})^{s}= \sum_{y \in S_{1}, y \le 2^{n-1}}y^{s}-(y+2^{n-1})^{s}$. It is clear from there.
nikolapavlovic
10.11.2017 17:21
Split all the numbers in groups based on the parity of the sum of it's digits in binary.From this (that is any of the generalizations listed there) we're done.