Anonymous
Anonymous asked in Science & MathematicsMathematics · 4 months ago

# Pigeonhole principle - hard math problems?

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 would appreciate any help.

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.)

Relevance
• atsuo
Lv 6
4 months ago

Think S as a set of chosen k integers from the set T = {1,2, ..., n}.

a.

x,y are integers, so "x-y=1" means "x and y are consequtive".

When n is even, ceiling(n/2) = n/2. And we can choose n/2 integers from T

so that any two chosen integers are not consequtive. For example, choose

1,3,6,8, ... ,n. But the distance between any two chosen integers can not

be larger than 3, so we can not choose any more integer.

When n is odd, ceiling(n/2) = (n+1)/2. Only if we choose 1,3,5, ... ,n-2,n

from T then we can choose (n+1)/2 integers so that any two chosen

integers are not consequtive. So we can not choose any more integer.

Therefore, if we choose k (k > ceiling(k/2)) integers from T then at least

two chosen integers become consecutive.

b.

There are kC2 ways to choose two different integers U,V (U<V) from S.

Let a pair of (U,V) be P and the value of V-U be D. There are kC2 pairs,

so let P(i) = (Ui,Vi) and D(i) = Vi-Ui for 1≦i≦kC2.

And we know 1≦Ui<Vi≦n so 1≦Vi-Ui≦n-1. That is, 1≦D(i)≦n-1.

So if kC2 > n-1 then the pairs P(i) and P(j) exist such that D(i) = D(j) (i≠j).

When P(i)=(a,b) and P(j)=(x,y) they become the elements a,b,x,y∈S such

that a≠b, {a,b}≠{x,y} and b−a=y−x.

c.

Let S = {s1,s2, ... ,sk} and s1<s2< ... <sk.

Divide S into S1 = {s1, ... ,st} and S2 = {s(t+1), ... ,sk} so that

|S1||S2| = t(k-t) is maximized. That is, if k is even then t(k-t) = (k/2)^2,

if k is odd then t(k-t) = ((k-1)/2)((k+1)/2). So it can be represented as

t(k-t) = floor(k/2)*ceiling(k/2).

There are floor(k/2)*ceiling(k/2) ways to choose an integer U from S1 and

an integer V from S2 (so U<V). Let a pair of (U,V) be P and the value of

V-U be D. There are floor(k/2)*ceiling(k/2) pairs, so let P(i) = (Ui,Vi) and

D(i) = Vi-Ui for 1≦i≦floor(k/2)*ceiling(k/2).

And we know 1≦Ui<Vi≦n so 1≦Vi-Ui≦n-1. That is, 1≦D(i)≦n-1.

So if floor(k/2)*ceiling(k/2) > n-1 then the pairs P(i) and P(j) exist such that

D(i) = D(j). It means Vi-Ui = Vj-Uj, so Uj-Ui = Vj-Vi and Ui-Uj = Vi-Vj stand.

If Ui<Uj then Uj-Ui>0 so Vj-Vi>0 and Vi<Vj. Therefore when (Ui,Uj,Vi,Vj)

=(a,b,x,y) they become the elements of 4-element subset {a,b,x,y}⊂S

such that a-b=x-y.

If Ui>Uj then Uj-Ui<0 so Vj-Vi<0 and Vi>Vj. Therefore when (Ui,Uj,Vi,Vj)

=(b,a,y,x) they become the elements of 4-element subset {a,b,x,y}⊂S

such that a-b=x-y.