0

You are given $n$ ($n$ is even) integers $a_0,a_1,\ldots,a_{n-1}$ representing temperature measurements, equally spaced around a circle. Since the points are "close", the temperature difference between two points next to each other is at most one. In other words, $|a_i-a_{i+1}|\leq 1$(for $i=0,\ldots,n-2$) and $|a_{n-1}-a_0|\leq1$.

Two points $i,j$ are opposite if $|i-j|\equiv n/2 \mod n$ (i.e. literally opposite on the circle). Define a function $D(i):=a_i-a_j$, where $j$ is the opposite point of $i$ (i.e. $j=i+n/2 \mod n$).

I'm trying to prove that there always exists a point $i$ such that $|D(i)|\leq 1$.

I think proof by contradiction is a viable option, and for that I would assume that $\forall i,|D(i)|\geq 2$. However, I don't really know how to condense my random ideas into a working proof for this problem. Can anyone help me? This is homework by the way.

user21860
  • 1
  • Hint 1: Suppose $D > 1$ at some point $i$. What is $D$ at the opposite point $j=i+n/2\bmod n$? Hint 2: How much can $D$ change between adjacent points $i$ and $i+1$? –  Sep 18 '14 at 01:17
  • @Rahul Ok, I thought about it a bit more with your hints. $D(i)=-D(j)$ by its definition. The function $D$ can change by at most 2 as you move from $i$ to $i+1$. So say you're at a point $i$. If $|D(i)|\leq 1$ then we're done. Otherwise, as we step around the circle to its opposite $j$, $D$ changes signs, which means we had to have gone through a point where $|D|\leq 1$. Is this on the right path? Is it rigorous enough? Thanks for your help! – user21860 Sep 18 '14 at 01:32
  • This is a related question you may find interesting.

    http://math.stackexchange.com/questions/715777/there-exist-two-antipodal-points-on-the-equator-that-have-the-same-temperature

     – JessicaK Sep 18 '14 at 01:39
  • You're almost there. You still have to argue that you can't get from $D>1$ to $D<1$ without passing through a point where $|D|\le1$, which is where you'll use the fact that $D$ changes by at most $2$ at a time. –  Sep 18 '14 at 04:07

0 Answers0