The Pigeonhole Principle

Pigeons: the 6 classes. Holes: the 5 weekdays (Mon–Fri). Each class meets on exactly one weekday. Since $6>5$, by the pigeonhole principle two classes meet on the same day. ∎

a) 2 colors (holes); to guarantee 2 in one hole: $2(2-1)+1=3$ socks.

b) Specific color, so think worst case: all 12 brown come out first, then 2 black: $12+2=14$.

Holes: (graduation year, major) pairs: $4\cdot 21=84$. To force two students into the same hole you need $84+1=85$.

Pigeons: the 5 integers. Holes: the possible remainders mod 4: $\{0,1,2,3\}$, which is 4 holes. Each integer has exactly one remainder. Since $5>4$, two of the integers have the same remainder when divided by 4. ∎

Let the integers be $a,a+1,\dots ,a+n-1$.

Their remainders mod $n$ are all different: if $(a+i)\mathrm{mod}n=(a+j)\mathrm{mod}n$ with $0\le i<j\le n-1$, then $n\mid (j-i)$. But $0<j-i<n$, which is impossible.

So the $n$ integers have $n$ distinct remainders, drawn from the $n$ possible values $\{0,1,\dots ,n-1\}$. Hence every remainder occurs exactly once. In particular remainder $0$ occurs exactly once: exactly one of the integers is divisible by $n$. ∎

$k=50$ boxes, want $r=100$: $N=k(r-1)+1=50\cdot 99+1=4951$.

(With 4950 students, each state could have exactly 99.)

The midpoint of $(a,b,c)$ and $(d,e,f)$ is $\left(\frac{a+d}{2},\frac{b+e}{2},\frac{c+f}{2}\right)$. It has integer coordinates exactly when $a,d$ have the same parity, $b,e$ have the same parity, and $c,f$ have the same parity.

Holes: parity patterns (even/odd for each coordinate): $2^3=8$ patterns. Pigeons: 9 points. By pigeonhole, two points share a parity pattern, and their midpoint has integer coordinates. ∎

a) Group $\{1,\dots ,8\}$ into 4 pairs that each sum to 9: $\{1,8\},\{2,7\},\{3,6\},\{4,5\}$. These are the holes. Choosing 5 integers (pigeons) puts two in the same pair, and those two sum to 9. ∎

b) No. Counterexample: $\{1,2,3,4\}$ (one from each pair) has no two summing to 9.

Pairs summing to 7: $\{1,6\},\{2,5\},\{3,4\}$, so 3 holes. Choosing 4 numbers forces two from the same pair. With only 3, you could pick $\{1,2,3\}$ and avoid it. Answer: 4.

Bins: $50\cdot 85\cdot 5=21,250$. To force two products into one bin: $21,250+1=21,251$.

a) Generalized pigeonhole: 25 students in 3 classes, so some class has at least $\lceil 25/3\rceil =9$. ∎

(By contradiction: if each had at most 8, the total would be at most $24<25$.)

b) Suppose not: at most 2 freshmen, at most 18 sophomores, and at most 4 juniors. Then there are at most $2+18+4=24$ students, contradicting 25. So at least one of the three conditions holds. ∎

Holes: (three initials, birthday) combinations: $26^3\cdot 366=17,576\cdot 366=6,432,816$.
Pigeons: 39,000,000 people.

Some hole contains at least
$$\lceil \frac{39,000,000}{6,432,816}\rceil =7\ge 6$$
people, since $6\cdot 6,432,816=38,596,896<39,000,000$. So at least six (in fact seven) people share initials and birthday. ∎

Holes: possible hair counts $1,2,\dots ,200,000$: 200,000 holes. Pigeons: at least 800,001 people.

• Since $800,001>200,000$, the pigeonhole principle gives two people with the same count.
• Generalized: some hole has at least $\lceil 800,001/200,000\rceil =\lceil 4.000005\rceil =5$ people. ∎

Some time period must hold at least $\lceil 677/38\rceil$ classes, and each needs its own room.
$38\cdot 17=646<677\le 684=38\cdot 18$, so $\lceil 677/38\rceil =18$.

So at least 18 rooms are needed, and 18 suffice (spread the classes evenly, at most 18 per period).

Each computer is connected to between 0 and 5 others: six possible values. But 0 and 5 can't both occur: if some computer is connected to all 5 others, then no computer is connected to 0 others, and vice versa.

So the six computers (pigeons) take at most 5 distinct connection counts (holes). By pigeonhole, two computers have the same number of connections. ∎

1620 suffice. Connect computer $C_k$ to printer $P_k$ for $k=1,\dots ,20$, and connect each of $C_{21},\dots ,C_{100}$ to all 20 printers: $20+80\cdot 20=1620$ cables. For any 20 computers, the ones among $C_1,\dots ,C_{20}$ use their own printers, and each of the others (connected to everything) takes one of the unused printers.

1619 do not suffice. With 1619 cables and 20 printers, some printer has at most $\lfloor 1619/20\rfloor =80$ cables (if all had $\ge 81$, there would be $\ge 1620$ cables). That leaves at least 20 computers not connected to it. Those 20 computers can reach at most the other 19 printers, so they can't all print at once.

Let $a_i$ = total matches completed by the end of hour $i$. Since there's at least one match per hour,
$$1\le a_1<a_2<\cdots <a_{75}\le 125,$$
and therefore
$$25\le a_1+24<a_2+24<\cdots <a_{75}+24\le 149.$$
That's $150$ numbers $a_1,\dots ,a_{75},a_1+24,\dots ,a_{75}+24$, all in $\{1,\dots ,149\}$. By pigeonhole two are equal. The $a_i$ are distinct from each other, and so are the $a_j+24$. So $a_i=a_j+24$ for some $i>j$. Then during hours $j+1$ through $i$ there were exactly $a_i-a_j=24$ matches. ∎

Pigeons: the $|S|$ elements of $S$. Holes: the $|T|$ elements of $T$. Place each $s$ into the hole $f(s)$. By the generalized pigeonhole principle, some hole $t\in T$ receives at least $\lceil |S|/|T|\rceil =m$ elements, i.e. there are distinct $s_1,\dots ,s_m$ with $f(s_1)=\cdots =f(s_m)=t$. ∎

Let $\{y\}=y-\lfloor y\rfloor \in [0,1)$ be the fractional part. Consider the $n+1$ numbers
$$\{0\cdot x\}=0,\{x\},\{2x\},\dots ,\{nx\}.$$
Split $[0,1)$ into $n$ boxes $\left[\frac{k}{n},\frac{k+1}{n}\right)$, $k=0,\dots ,n-1$. With $n+1$ numbers in $n$ boxes, two land in the same box: $\{ix\}$ and $\{jx\}$ with $0\le i<j\le n$, and $\left|\{jx\}-\{ix\}\right|<\frac{1}{n}$.

Now $(j-i)x=(\lfloor jx\rfloor -\lfloor ix\rfloor )+(\{jx\}-\{ix\})$, an integer plus something of absolute value $<1/n$. So $(j-i)x$ is within $1/n$ of an integer, and hence its nearest integer is within $1/n$ too. Take $j^{\prime }=j-i$, which satisfies $1\le j^{\prime }\le n$. ∎

a) 4 suits, want 3 in one: $4(3-1)+1=9$. (8 cards could be 2 of each suit.)

b) Specific suit, so worst case: all $39$ non-clubs first, then 3 clubs: $39+3=42$.

c) 13 ranks: $13+1=14$.

Write each chosen integer as $a=2^{k}m$ with $m$ odd (factor out all 2s). Since $a\le 2n$, the odd part $m$ is one of $1,3,5,\dots ,2n-1$: only $n$ possible values (holes).

With $n+1$ integers (pigeons), two have the same odd part: $a_i=2^{k_i}m$ and $a_j=2^{k_j}m$ with $k_i\ne k_j$ (the integers are distinct). If $k_i<k_j$, then $a_j=2^{k_j-k_i}{a}_i$, so $a_i\mid a_j$. ∎