Proof: Over 100 Pairs of Shoes in a Factory

[T@P]

a factory has a total of 600 shoes. 300 left shoes, and 300 right shoes. they come in 3 sizes. you know there are 200 of each size. prove that there are at least 100 *pairs* of shoes. if you have two shoes, they are only a pair iff they are of the opposite type (left/right) and the same size.

hint you should use the pidgeon hole principle

 

[AKG]

Let the number of pairs be X. Remove them, and you are left with 600 - 2X shoes, and you know 300 - X of them are left, 300 - X of them are right. We need to show that it is impossible for X < 100. Now, if X < 100, then there are at least 402 shows remaining, and since there are only 200 of each size, there are at least 2 of any given size, i.e. every size is represented in the remaining bunch. There must be some size of shoe for which at least \left\lceil{200 - 2X/3}\right\rceil remain. Suppose the one with the most remaining has Y + \left\lceil{200 - 2X/3}\right\rceil remaining. Without loss of generality, let them all be left. Remove them, and we're left with (300 - X) - (Y + \left\lceil{200 - 2X/3}\right\rceil ) left and 300 - X right, each shoe being 1 of 2 possible sizes.

Now:
(300 - X) - (Y + \left\lceil{200 - 2X/3}\right\rceil )
&gt; 200 - (Y + \left\lceil{200 - 2X/3}\right\rceil) since X < 100
\geq 0 since (Y + \left\lceil{200 - 2X/3}\right\rceil) is the number of shoes of some given size, and thus can't exceed 200.

So, there is at least 1 left shoe, and:

300 - X &gt; 200 since X < 100

So there are at least 201 right shoes, and recall, all of these shoes are one of 2 sizes. If there are 201 right shoes, then both sizes must be represented in this bunch, otherwise one size would have 201 shoes, which isn't allowed. Therefore, since both sizes are in this bunch, then there must be a remaining match with the remaining left shoe(s). This contradicts the assumption that there were X pairs (now we have X + 1). This contradiction means that the assumption X < 100 is wrong.

 

[Galileo]

Well, take 6 shoes, suppose there are 3 left ones and 3 right ones, 2 small, 2 medium and 2 large.
Here there always exists a pair, since the 3 left ones come in at least 2 sizes (e.g. 2 small, 1 medium). The same for the 3 right ones, so one of the sizes of the left shoes must be the same as one of the sizes of the right shoes.

Given this, you can easily group the 600 shoes into 100 groups of 6 shoes each as above (3 left, 3 right and 2 of each size). In each of these groups is at least one pair, so the total has at least 100 pairs.

 

[BicycleTree]

Another way: For a given arrangement X of shoes, assume that the # of right shoes of size 1 >= # of right shoes of size 2 >= # of right shoes of size 3; otherwise, renumber the sizes so this is true.

Start with 200 right shoes of size 1, 200 left shoes of size 3, and 100 left and 100 right of size 2. This makes 100 pairs. X can be arrived at by swapping some number between 0 and 100 of left shoes from 2 to 1 and swapping some number between 0 and 100 of right shoes from 2 to 3. First swap (left shoes) from 2 to 1: every swap reduces the number of pairs in 2 by 1 and increases the number of pairs in 1 by 1. Then swap right shoes from 2 to 3: every swap increases the number of pairs in 3 by 1 and it either decreases by 1 (if 2 has as many or more left shoes than right shoes) or increases by 1 (if 2 has fewer left shoes than right shoes) the number of pairs in 2. So every swap to arrive at X from the original 200, 200, 100-100 arrangement either does not affect or increases the number of pairs. So the number of pairs in X is at least 100.

Edit: corrected flaw (which did not affect the outcome)

 

[BicycleTree]

Also from my way of doing it you can tell that the number of pairs will always be even--since each swap from the initial arrangement increases the number of pairs by 0 or +2.

 

[T@P]

actually i like galileo's solution alot; but techincally you should use the pidgeon hole principale ;)
anyway, the way i did it was also sort of long, but to give you the idea it was just to assume (wlog) that one size has more left shoes then the rest, (lol) and using that to essentially get rid of one size and only work with two... if its not clear its ok, galileo and AKG have excellant solutions too :)

 

[BicycleTree]

actually i like galileo's solution alot; but techincally you should use the pidgeon hole principale ;)
anyway, the way i did it was also sort of long, but to give you the idea it was just to assume (wlog) that one size has more left shoes then the rest, (lol) and using that to essentially get rid of one size and only work with two... if its not clear its ok, galileo and AKG have excellant solutions too :)

Gee, thanks!

 

[BicycleTree]

Perhaps I wasn't clear enough. Here's a more symbolic representation of my argument:

// in a distribution D of shoes, let a be the number of right shoes of size 1, b
// be the number of right shoes of size 2, and c be the number of right 
// shoes  of size 3, with a >= b >= c

x = 200;
y = 100;
z = 0;

// x, y, and z represent the number of right shoes in groups X, Y, and Z, each of 200 shoes.

for(int i = 0; i <=100; i++)
{
     if (x == a) break;
     x--; // increases # of pairs in group X by 1 since x > 100 at start of line
     y++; // decreases # of pairs in group Y by 1 since y < 100 at start of line
}

// now x == a (since a >= b >= c, a >=100 and the loop will only terminate by the break statement)

for(int i = 0; i <=100; i++)
{
    if(z == c) break;
    z++; // increases # of pairs in Z by 1 because z < 100 at start of line
    y--; // decreases or increases # of pairs in Y
}

// z == c (since c <= b <= a so c <=100 and the loop only terminates on the break statement)

// Now x == a, z == c, and so y == b, and since in every iteration of every loop the
// # of pairs in X + the # of pairs in Y + the number of pairs in Z did not change or increased (from an initial value of 100), the # of pairs in D >= 100
// And since when the # of pairs increased it was always by 2, the # of pairs in D is even

I am saying that things "increased" or "decreased" to mean that the newest value named by them is greater than or less than the second-newest value named by them. I haven't had a course in algorithmic proof yet so this is just how I say it.

 

[BicycleTree]

Incidentally--how would you prove that the number of pairs must be even without using an algorithmic argument?

 

[Alkatran]

Worst case scenario is:
200 left large shoes
200 right small shoes
100 pairs of medium shoes

If you swap any shoe you end up with more pairs. 1 left large for 1 medium right gives you a large pair (swapping for a left leaves you where you started) etc...
Since this is the worst case the number of pairs must be at least 100.

 

[BicycleTree]

That's the same idea I used for my proof, Alkatran, but you have to show that it is worst case not only locally but for switching any amount of shoes.