Mathematics Asked by MNIShaurya on January 18, 2021
The problem:
$S$ is the set ${1,2,…,10^6}$. Show that for any $101$ element subset $A$ of $S$ we can find $100$ distinct elements $x_i$ of $S$ such that the sets:
{$a + x_i$$|$$a in{A}$} are pairwise disjoint
Solution:
Form the set ${a_1, …, a_{101}}$. Say we have four $i, j, k, m$ such that:
$a_i + x_k = a_j + x_m$
$a_i – a_j = x_m – x_k$
There are atmost ${101 choose 2}$ possible LHS and ${100 choose 2}$ possible RHS. There are atleast $10^6 – 1$ possible differences of the set $S$ ($k – 1$ for $1 < k ≤ 10^6$)
If we can assign a set of differences to RHS none of which are in the set of differences of LHS, then the proposition is true. We can do this if:
${101 choose 2}$ $+$ ${100 choose 2}$ $≤$ $10^6 – 1$
Which is indeed true.
I’d like this to be checked. I haven’t seen the official solution, so if it happens to match with that, do tell me.
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP