1
$\begingroup$

I have two questions about the following problem, taken from Challenging Problems in Algebra by Posamentier and Salkind: (1) Why is the answer not 1 person? (2) The answer given, without solution, is 26. Is the correct answer not 27?

Assume that every resident of a city with population 8,000,000 has at least 1 hair on his or head but not more than 300,000 hairs. What is the least number n in the assertion that there are n persons in the city with the same number of hairs on his or her head?

Yesterday a student of mine asked (1), arguing that, theoretically, it is possible for 1 person to have $a$ hairs on his or her head and for 7,999,999 people to have $b$ hairs on their heads, $a \not= b$ and $1\leq a \leq 300,000$, $1 \leq b \leq 300,000$. What is wrong with this argument?

What is wrong with the following solution, which gives 27? Assume that each of the 300,000 possible numbers of hairs corresponds to disjoint sets of 26 people. This accounts for $26 \times 300,000=7,800,000$ people. Now, for some 200,000 of the 300,000 possible numbers of hairs, assign 1 more person. Those 200,000 numbers of hairs will all have 27 people associated with them, and this accounts for the whole population. Thus, in the scenario where every resident has $a$ hairs or $b$ hairs, $\max(a,b) \geq 27$.

$\endgroup$
  • $\begingroup$ Surely the problem means to ask for the "greatest number n" that works, no? I mean, n=1 works. And I don't understand the point of your student's argument. Yes, that scenario is possible...and in that particular case $n=7,999,999$. But other scenarios are possible as well. I agree with $27$ for the general problem. $\endgroup$ – lulu Sep 30 '15 at 21:21
  • $\begingroup$ Ah, I'm wrong. The problem is asking "Find the least integer $n$ such that we can be sure that there is a group of 'equal-haired' individuals of size not greater than $n$". That makes sense and for that the answer is $26$...your argument proves it! in your (optimally uniform) collection you have $200,000$ cohorts of size $27$ and $100,000$ cohorts of size $26$. Hence there are cohorts of size $26$. $\endgroup$ – lulu Sep 30 '15 at 21:33
1
$\begingroup$

To summarize: given the data, the problem is asking "find the smallest integer $n$ such that there is always a cohort of size $≤n$". The answer to that question is $26$.

To see that, note that there are examples with no cohort of size $25$ (or smaller): Just take $26$ people with each of the possible $300,000$ hair numbers and distribute the "excess" $200,000$ individuals among these cohorts anyway you like.

On the other hand, it is clear that it can not be the case that there are scenarios without cohorts of size $26$ or smaller; for were it otherwise each cohort would have at least $27$ individuals in it and that would require at least $8,100,000$ individuals.

Note: a related question (which on first reading is what I thought was being asked here) would be "find the greatest integer $m$ such that we are guaranteed to have a cohort of size $≥m$". The answer to that is $27$, and the argument is as given by the OP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.