A Walk Through Combinatorics 4th Ed. 1. 33.

 If I had a typed solution, I lost it - sorry.

___

pf.: Partition [2n]={1,2}U{3,4}U...U{2n-1,2n}. These are n disjoint sets (i.e., 'boxes') into which we will place n+1 different integers (i.e., 'balls'). Hence, by the Pigeon-Hole Principle some {i,i+1} gets two integers. Now of course (i,i+1)=1 and we are done.

[]