Can someone please explain how I would solve these using the pigeonhole principle? I know that the principle basically states if k+1 or more objects are placed into k boxes, then there is at least one box containing two or more objects. I'm just really lost on how to do these though because they seem really mathematical and complex.
I'm not even sure how troublesome the solutions to these are so, I apologize if it seems like a lot. I'd appreciate any help with solving these, or even if it's just the first one. I think if I got the general idea of how to solve these types of questions, I'll have an easier time solving the rest. I'm just having trouble visualizing them.
a. Let S be a k-element subset of {1,…,n}. Prove that, if k>⌈n/2⌉, then there exists x,y∈S such that x−y=1.
b. Let S be a k-element subset of {1,…,n}. Prove that, if (kC2)>n−1, then there exists a,b,x,y∈S such that a≠b, {a,b}≠{x,y} and b−a=y−x. (Note that it may be the case that b=x or a=y.)
c. Let S be a k-element subset of {1,…,n}. Prove that, if ⌊k/2⌋⋅⌈k/2⌉>n−1, then there exists a 4-element subset {a,b,x,y}⊂S such that a−b=x−y. (Unlike the previous question, a,b,x,y must be 4 distinct elements.)
Hints:
a. If no elements of $S$ differ by $1$, that means they are all odd or all even.
b. There are $\binom{k}{2}$ pairs in $S$. For each pair, write down the [positive] difference between the two numbers (e.g., for the pair $\{2,4\}$ write down $2$; for $\{3,7\}$ write down $4$). What possible differences can there be? Why must some difference appear more than once?