Need help with this problem(mp based on PigeonHole Principle)

62 Views Asked by At

given a set S with distinct elements $s_{0}, s_{1},s_{2}.. s_{99}$, $s_{i} \in [0, 10^6] $ we have to construct 100 sets T1,T2,T3,T4.. T100, such that

$ T1=[s_{0}+t_{1},s_{1}+t_{1},s{2}+t_{1},... ,s_{99}+t_{1}] $

$ T2=[s_{0}+t_{2},s_{1}+t_{2},s{2}+t_{2},... ,s_{99}+t_{2}] $

.

.

.

$T100=[s_{0}+t_{100},s_{1}+t_{100},s{2}+t_{100},... ,s_{99}+t_{100}] $

We need to prove that we can choose $t_{1}, t_{2}, t_{3} ... t_{100}$ with $t_{i} \in [0, 10^6]$such that all the elements of S, T1, T2, T100 are unique.

I guess this can be solved by the pigeon hole principle, but not able to think what are the pigeons and what are pigeonholes.

I also thought that there are $50\times99$ difference terms in S. Each $ t_{i} $ should be different from these terms.Also $(s_{j}-s_{k}) != (t_{m}-t_{n})$ for all m,n j,k. I am not able to continue form here. Now there cannot be $50\times99$ unique difference because then $s_{99}$ would be greater than 1e6.

We can think of it as a series of 99 numbers, we have to create a series of 99 numbers such that the sum of any consecutive terms of the first series can't be equal to sum of any consecutive terms of the second series.