There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to prove that there are always two adjacent vertices (two vertices that are connected by an edge) whose number differ by 48 or less.
To prove this, I consider the vertex that is assigned the integer $50$. It has 3 'neighbors' and there are only 3 numbers in the given set that differ by more than 48 from 50: $1$, $99$, $100$.
Now there's 3 possible cases: each of the numbers can be on the 'opposite' side of the prism. For 1 and 99 it is easy to show that there are adjacent vertices that differ by 48 or less. In ASCII art:
100---50---99
| |
1----X
X > 1+48=49 and X < 99-48=51 which would mean that X=50, however the integer 50 was previously assigned. Subsequently there are edges that differ by 48 or less.
100---50---1
| |
99---X
Here we have the exact same problem. X would need to be 50, but 50 was already assigned.
If we, however, choose 100 to be on the opposite side, I run into a problem:
1---50---99---48 ... 2---X
| | | | ... |
51--100--49---98 ... 52
I need a terribly long 'chain' to get to a conflict and I assume this is not the nice or good way of proving the statement in question. Please enlighten me!
Let $(n,m)$ mean that $n$ and $m$ are on opposite parts of the prism from each other and let $A_n$ be the allowable set of neighbors for $n$ - the numbers that are more than 48 away from $n$ and that haven't been given as labels already.
You deduced that since 50 is in the middle of [1,100], $A_{50}=\{1,99,100\}$ and then by case breakdown that we must have $(50,100)$. Since there are an even amount of numbers in that range, however, we actually get two "middle" numbers, 51 being the other. By the same reasoning we then have that $A_{51}=\{1,2,100\}$. This shows that 50 and 51 have to share 1 and 100 as neighbors, which forces us to have $(1,51)$. This in turn forces the location of 2.
We can now play the same game with the "next-most middle" numbers, 49 and 52. $A_{49}=\{98,99,100\}$ and $A_{52}=\{1,2,3\}$. Since 1, 2, 99, and 100 are already placed, this forces the location of 49 and 52, as well as the remaining values in their allowable sets. Continue on in this way, expanding out from the middle of the range. At each point your placements are forced. You will then start to see a pattern in the placement of the labels. What happens at the point where the two "ends" that are expanding out from $(50,100)$ meet? What conclusion can you draw from this?