TransWikia.com

(proposed) elegant solution to IMO 2003 P1

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.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP