Prove that there are at least 100 pairs of usable boots

Question

A store has 200 boots of size A, 200 boots of size B and 200 boots of size C. Among these 600 boots, 300 are of the left foot and 300 are of the right foot. Knowing that usable pairs of boots have the same size and are for different feet, prove that it's possible to find at least 100 pairs of usable boots.

Answer 1

If any size category $A,B,C$ has equal numbers of left and right boots, there are the required $100$ pairs of usable boots and we are done.

Otherwise every size will have a majority of one foot. Since $101\times 3>300$, these cannot all be the same foot, so without loss of generality we can assume that there are two right-foot majorities and one left-foot majority. Now the number of right boots in the right-foot majority sizes is at most $300$, so there are at least $100$ left boots in those two sizes, which can all be matched to right boots, giving us $100$ usable pairs as required.

Answer 2

To give you a feel for the problem, here is a proof by cases. Calling $a_L$ the number of size $A$ left foot boots, $b_R$ the number of size $B$ right foot boots, etc.

We first note that the number of pairs of type $A$ is given by the $\min\{a_L,a_R\}$. Now, we have $a_L + a_R = 200$, hence $a_R = 200-a_L$. We can use this to say the number of pairs of size $A$ is given by $\min\{a_L,200-a_L\}$.

Now, calling $p$ the number of pairs we see clearly that

$p = \min\{a_L,200-a_L\} + \min\{b_L,200-b_L\} + \min\{c_L,200-c_L\}$.

Assume that the left-footed shoe is the lesser quantity in all of these terms then we get $p = a_L + b_L + c_L$, but we know there are 300 left-footed shoes, hence $p=300$. Assume that the left-footed shoe is the lesser quantity in two of the terms of $p$. Without loss of generality, assume that this is true for size $A$ and $B$. Then we have that

$p = a_L + b_L + 200 - c_L = 300 - c_L + 200 - c_L = 500 - 2c_L$,

but $c_L \leq 200$ hence, $p\geq 100$. Assume that the left-footed shoe is the lesser quantity in one of the terms of $p$. Without loss of generality, assume that this is true for size $A$. Then we have

$p = a_L + 400 - (b_L + c_L) = a_L + 400 - (300 - a_L) = 100 + 2a_L \geq 100$.

Lastly, assume that the left-footed shoe is the lesser quantity in none of the terms of $p$. Then

$p = 600 - a_L - b_L - c_L = 300$.

Answer 3

(Alternative solution)

Let $\alpha, \beta,\gamma \in \mathbb Z\leq 100 $

Number of boots are tabulated as follows:

$$\begin{array}&& \hline \bf\text{Left}&\bf\text{Right}&\bf\text{Total}&\bf\text{Usable Pairs}\\ \hline \bf\text{Size A}&100+\alpha &100-\alpha &200&100-\alpha\\ \bf\text{Size B}&100-\beta &100+\beta &200 &100-\beta\\ \bf\text{Size C}&100+\gamma &100-\gamma &200 &100-\gamma\\ \hline \bf\text{Total}&300 &300 &600&300-(\alpha+\beta+\gamma)\\ \hline \end{array}$$

For total Left and Right boots to equal $300$ each, $\alpha-\beta+\gamma=0 \Rightarrow \beta=\alpha+\gamma$.

Number of usable pairs is given by $$\begin{align} N=300-(\alpha+\beta+\gamma)&=300-2\beta\\ N_{\text{max}}=N\big|_{\beta=0}&=300\\ N_{\text{min}}=N\big|_{\beta=100}&=100\\ \end{align} $$

---

(Original solution below)

Consider the extreme case where

• all 200 size A boots are Left (L), and
• all 200 size B boots are Right (R),

i.e. all unusable.

This leaves 100 R and 100 L boots. These must all be of size C.

Hence there are 100 pairs of usable boots.

Answer 4

There are three categories- size A shoes, size B shoes, and size C shoes. We are going to place 600 boots into these three categories. Since 300 shoes are of the left foot, by the pigeon-hole principle, at least one category will contain 100 left boots. Now we add in the 300 right boots.

Here's the kind of naive way I thought about this problem. The category containing at least 100 left boots has between 100 and 200 left boots- call this category $c_1$. Now there are around 100 cases.

If $c_1$ contains 200 left boots, then the remaining 100 are contained in the second two categories which when we fill with right boots will yield 100 pairs of working shoes since neither of these categories will have fewer than 100 spots for right boots.

If $c_1$ contains 199 left boots, then the remaining 101 are contained in the second two categories, and we get 1 working pair from $c_1$. If all 101 are contained in one of the remaining two categories, then that category will yield 99 additional working pairs after being filled with right boots. If neither of the remaining two categories contain all 101 left boots, then we get an additional 101 working pairs, since both categories have at least 100 remaining spots for right boots.

If $c_1$ contains 198 left boots, we repeat the above argument.

This kind of argument will work for $c_1$ containing 200 down to 100 left boots.

There is probably a more elegant way of proving this, but I find this first glance type of reasoning more intuitive and still reasonably rigorous.