Hard Pigeonhole Principle Modulus Distance

71 Views Asked by At

Prove that when $11$ real numbers between $0$ and $1$ are chosen, there exist $x_i$, $x_j$, $x_k$ and $x \in [0,1]$, such that |$x-x_i| \leq 0.1$, |$x-x_j| \leq 0.1$, |$x-x_k| \leq 0.1$.

I will only write the main ideas of my proof. Can someone tell me if it is correct ? I basically said there are $5$ pigeonholes, $A$ such that $0 \leq x_i < 0.2$, B such that $0.2 \leq x_i < 0.4$, all the way up to E such that $0.8 \leq x_i \leq 1$.

Then by pigeonhole principle there exists some pigeonhole with at least $3$ numbers. Thus, there must exist some $x \in [0,1]$, such that the max distance between each of the $3$ numbers and $x$ is $0.1$

1

There are 1 best solutions below

2
On

Your proof is alright. Using $5$ pigeonholes as you did was the best, as you wouldn't need extra casework. At any rate, the pigeonhole principle states that for natural numbers $k$ and $m$, if $n = km + 1$ objects are distributed among $m$ pigeonholes, then at least one of the pigeonholes will contain at least $k+1$ objects. Here, we have $n=11$, and $k+1=3$, so this suggests that we want $m=5$ pigeonholes. (Note, for harder questions you'd need to be more creative)

To improve the notation in your answer, I would just say that the sets are the intervals $[0,0.2)$, $[0.2,0.4)$, $[0.4,0.6)$, $[0.6,0.8)$, and $[0.8,1]$.

To be extra explicit, you could say that the final $x$ would be chosen as the midpoint of an interval with $3$ or more numbers, defined as $(a+b)/2$ where $a$,$b$ are the endpoints of the interval.