During the Fashion Week in NY 50 fashion-forward women attended a new hot Japanese designer show. As customary in the Asian tradition, they were asked to take off their shoes before entering the showroom. There was a large pile of expensive designer shoes at the door. When leaving, each of the women picked a pair she most fancied and was able to fit in (some took shoes much larger than their size).

What is the best and worst outcome in terms of number of women left shoe-less and number of shoes that no one can fit in?

Your answers are accepted any time until midnight Eastern Time on Sunday, on our Family Puzzle Marathon.

Top image by geishaboy500, distributed under CCL.

## 6 comments:

If we were given a range of shoe size for the women, we could have done a normal curve , look at the standard deviation and the average to see were 95% of the women are in term of shoe size. Then we could compare the sizes we got in term of designer shoes.

We have no data and we don't even know where was the show and from where these women came from. Imagine American women in a show in Japan.

I think we are missing important information.

I will say that the best outcome is that before the show, they planed to give new shoes and ask for the women shoes sizes such that each of them find one pair that fits and they like. The worst one will be that the shoes sizes are in the 5% under the normal curve.

If all of the women have the same shoe size, the best outcome is all 50 women just trading shoes.

The puzzle does say that some women took shoes much larger than their size so I am assuming that they are not all the same size. The best case in this scenario is 49 women getting shoes that fit them and 1 woman being left shoe-less (for instance, the woman with the largest feet has shoes that have been claimed and now that woman cannot fit into any other shoes).

The worst case scenario is 25 women going home shoe-less because they have bigger feet than the other 25 women. The 25 women with smaller feet all pick the shoes of the 25 women with bigger feet.

If we try to find a scenario where 26 women go home shoe-less (say 24 women have smaller feet) then the 24 women will all choose bigger shoes but there will be 2 pairs leftover that 2 of the 26 women can fit in (though they may not be the ones she most fancied) - the same reasoning can be applied for any number > 25 women.

Technically if nobody fancies any other shoes, all 50 women could go home shoe-less but I doubt that would happen.

The very best solution would come about if all the women had the same size feet. Then the only problem is who gets what. I think you've eliminated that possibibility, but I like it.

The next possiblity is that everyone has a different size shoe. With 50 people that isn't possible, but this is math not fashion. That being the case 1 person would be left out, the one with the largest shoe size. She can't go down while everyone else moved up (say one size). No one is allowed to go up more than 1 size -- otherwise it creates havoc and the chain is broken.

Note: In the United States there are 20 different shoe sizes including 1/2 sizes which range from 4 to 14. The median and mode are pretty close to 7 to 7 1/2. If anyone is interested, I can post the breakdown.

But that brought me to the next condition. Suppose there are x different sizes of shoes and the number of people in each group of x is an even number. That would mean that my first solution applies because in each group, all anyone would have to do is exchange with someone else in the group. Or at least everyone would be confined to the group.

Even with an odd number of people the problem is doable. Suppose a group consists of A B and C

A will take B's shoes

C will Take A's shoes

B will C's shoes. Everyone is happy.

The real problem comes if everyone must choose a size that is not their own. They can go up, but not down, is what I'm reading.

If that happens then the worst case happens when there are 49 shoes smaller than the 50th shoe. Only 1 person can be satisfied; the other 49 will have to go home barefoot in the park.

One way to get a bad result is for the person with the smallest feet to take the shoes belonging to the one with the largest. That means the largest cannot take anything. Then the person with the second smallest foot size takes the next largest and so on down the line. Wouldn't that mean that after 25 pairs of shoes have been taken, no more can be? I'm actually kinda stuck.

Best case scenario would obviously be when no one goes barefoot. This may happen, for example, if everyone has same size (unlikely) or if everyone takes their own shoes (stranger things happen!).

Worst case scenario is half of women go barefoot. The simplest case demonstrating this is if you have 25 wearing size A and the other 25 wearing a larger size B. Group A then takes shoes of group B, leaving B out of luck since they can't wear A's smaller size. Is this really the worst case scenario? Let's prove that it is, by contradiction. Let's assume that there is a scenario when 24 women found shoes they could wear and 26 did not. The 26 must all have larger foot size than any of the remaining 26 pairs. But this is not possible because by definition of a "median". When considering a median of foot sizes, at least one of the 26 women would have to have foot size below the median - let's designate her as W. When considering a median of shoe sizes, at least one of the 26 pairs must have size above the median - let's designate that pair as P. Now, since all 50 women wore the 50 original pairs, the median of shoe sizes is at least the same (or larger) as the median of foot sizes. And therefore, W, being below foot size median would be able to fit into P, which is above shoe size median. QED.

I know, the puzzle looks intimidating with all those funky designer shoes. But in fact it is much simpler than it seems.

As most of you figured out the best case scenario is when everyone has the same size or when each woman picks her own shoes. Then no one will be left shoe-less. (I know I wrote that at least some women were wearing other women's shoes, larger shoes. In this case, instead of 0 the best case scenario is 1.)

The worst-case scenario is when half of the women are left with no shoes they can wear, as most of you figured out.

The easiest way to visualize this is to arrange all the shoes by size, from smallest to largest.

Now, stand every woman in front of her shoes.

If the first half of the women (25) that came with the smaller shoes will pick the larger 25 shoes of the second half of the women. Then all the women that came with the larger 25 pairs of shoes will have nothing to go home in. The shoes left will be the 25 smaller pairs of shoes.

Ilya and Wang drew a very interesting explanations of why anything more than 25 is impossible.

A puzzle point for everyone who dared to answer. Have a great week!

## Post a Comment

Note: Only a member of this blog may post a comment.