The Barberland Institute of Trichodemographic Research has published the following results:

  • Nobody in Barberland has more than 1,000,000 hairs.
  • No two inhabitants of Barberland have the same number of hairs.
  • Nobody in Barberland has the same number of hairs as the sum of two other inhabitants' hairs.

What is the maximum population of Barberland? Please, explain why.

  • 1
    $\begingroup$ This question is to simplistic. Add a fourth bullet to at least make people think. - 3 of the inhabitants contain 0, 1 and 2 hairs. $\endgroup$
    – Dunk
    Apr 27, 2015 at 18:37
  • 3
    $\begingroup$ To the bounty: What strikes you as unrigorous about xnor's answer? $\endgroup$ May 7, 2015 at 0:15
  • 1
    $\begingroup$ @Meelo xnor's answer is certainly valuable in that it presents a useful approach, but have you read it? "Then, out of each pair $\{k,n-k\}$, only one number of hairs can be present" is arguably not the case. $\endgroup$
    – GOTO 0
    May 7, 2015 at 10:19
  • $\begingroup$ As OP I feel uncomfortable pointing out every single mistake in the answers so far, but I really appreciate the efforts. Thanks so much for your solutions. $\endgroup$
    – GOTO 0
    May 7, 2015 at 10:22
  • $\begingroup$ Should we assume that hair count is an integer value? $\endgroup$
    – tfitzger
    May 11, 2015 at 15:44

7 Answers 7


The maximum number of inhabitants is

500,001 (+1 extra, see end of answer)

This is achieved by

Inhabitants with each number of hairs from 500,000 to 1,000,000.

This is optimal because

Let $n$ be the highest number of hairs any inhabitant has. Then, out of each pair $\{k,n-k\}$, only one number of hairs can be present since they sum to $n$. There are $\lfloor n/2 \rfloor$ pairs, counting the single-value "pair" when $k=n/2$ for even $n$. So, this gives at most $1 + \lfloor n/2 \rfloor$ inhabitants, and $n$ is at most 1,000,000.

Edit: Commenters pointed out that I made a mistake:

You can also add a bald person with 0 hairs, for 500,002 inhabitants total.

  • 13
    $\begingroup$ At the very least, you've missed one. Here's a hint - it only says that no inhabitant has the same number of hairs as the sum of two others. This permits a special case. $\endgroup$
    – Glen O
    Apr 27, 2015 at 11:17
  • $\begingroup$ ^ Lemme guess, one person is completely bald? $\endgroup$
    – user88
    Apr 27, 2015 at 15:31
  • 2
    $\begingroup$ I'm guessing this is wrong as there can be more. For example you can instead of having one person with 999997 hairs have one with 499999 and one with 499998 instead giving you one more person. Instead of having a person with 999993 hairs instead have one with 499997 and one with 499996 giving another extra person. Etc.... $\endgroup$
    – Crispy
    May 7, 2015 at 13:55
  • 3
    $\begingroup$ But then you run into (for example) the issue that 500000 + 499999 = 999999. As far as I can tell, every number you bring in below the median (500000) necessitates removing the current maximum number - 1 (999999) $\endgroup$ May 7, 2015 at 15:45
  • 1
    $\begingroup$ @Crispy Once you add the person with 4 into the population, they count for everyone. So P1 = 4, p2 = 500,000 and p3 = 500,004. If you can make any of these fit the form Px + Py = Pz, you have to remove one of the three people. In your example, x = 1, y = 2 and z = 3. P1 + P2 = P3. One of your three people is invalid. $\endgroup$
    – tfitzger
    May 11, 2015 at 15:41

A) Nobody in Barberland has more than 1,000,000 hairs.

No effect on population... yet.

B) No two inhabitants of Barberland have the same number of hairs.

Given A and B, we have no more than 1,000,001 people, since we know that there's no such thing as negative hair count, and 0 hairs is possible.

C) Nobody in Barberland has the same number of hairs as the sum of two other inhabitants' hairs.

'Other' inhabitants indicates that as long as oneself is part of the equation, then the rule doesn't apply. So we can have a 0 hair person.

Probably the easiest maximal count, then, is to start at 500,000 and continue on to 1,000,000, giving 500,002 total people, including the bald person.

  • 1
    $\begingroup$ But why is that maximal? $\endgroup$
    – reo katoa
    Apr 28, 2015 at 2:00

This is the rigorous proof asked by the author:

Ignore the 0 for now and consider only the interval $a=[1...1000000]$.
For any strategy, define $b$ as the set of elements accepted by our strategy (we've already proven that a cardinality of $b$ equal to 500001 is acceptable).
Now consider the highest number in the set $b$ and call it $n$: the number $n$ is the sum of $\frac{n-1}{2}$ different couples of natural numbers, and every number in the interval $[1...(n-1)]$ is present in one (and only one) of these couples. (see the note below).
If you don't want to have a contradiction, you can include in $b$ up to one number for each couple (indeed, if you include both, their sum would be $n$).
A consequence is that, given $n$, there are at most $\frac{n-1}{2}$ elements of $b$ before $n$, and no element of $b$ greater than $n$ because of our initial assumption.
As you can see, the maximum number of elements belonging to $b$ is $(1+\frac{n-1}{2})$ (that 1 is the number $n$, don't forget it!). It depends only on the highest number of $b$, so the optimal strategy has at most $(1+\frac{999999}{2})$ elements. How do we round $\frac{999999}{2}$? Round up, of course, since 999999 elements form 499999 couples and 1 standalone (see the note below)!
So, the maximum is 500001!
Ah, we forgot the zero! Then add 1 to the solution, which becomes $500002$


Note: If $(n-1)$ is odd, the couples are actually $\frac{n-1-1}{2}=\frac{n-2}{2}$ because the middle number remains out of any couple (you can't add it to itself!). For example, if $n=8$, the couples are {1,7},{2,6},{3,5}. Indeed, {4,4} isn't acceptable!

  • $\begingroup$ You are right, I was thinking about that myself,but you have posted it earlier than myself-only I forgot 0(bald). $\endgroup$ May 7, 2015 at 7:36
  • 3
    $\begingroup$ 500001 factorial? This answer is wrong! ;-)) $\endgroup$ May 9, 2015 at 8:16
  • 2
    $\begingroup$ That's not a factorial ahahahah! $\endgroup$
    – leoll2
    May 9, 2015 at 10:42
  • $\begingroup$ Well, in your last note, it should be $n=8$ for $\{1, 7\}$ to be valid. Indeed, you could get rid of that note completely if you say that there are $\lfloor\frac{n-1} 2\rfloor$ unordered pairs of distinct natural numbers summing up to $n$. $\endgroup$
    – GOTO 0
    May 13, 2015 at 14:43
  • $\begingroup$ @GOTO0 You're right, I'll edit now. Thanks! $\endgroup$
    – leoll2
    May 13, 2015 at 15:59

The answer is


One way of doing it is:

Pick every odd number. As the sum of 2 odds is even, we have 500,000 valid people. Also, we can have a person with 2 hairs. Also AdamDavis just reminded me that a bald person is allowed, so we can add the bald person to our population.

  • 10
    $\begingroup$ You can't have the person with 2 hairs unless you skip every other odd number. $\endgroup$
    – Rob Watts
    Apr 27, 2015 at 16:09
  • $\begingroup$ Instead of 2 hairs, you can have someone with 1,000,000 hairs. I like this answer the best because it's the simplest. $\endgroup$ May 8, 2015 at 19:15
  • $\begingroup$ @RobWatts Yes, my answer is wrong and I can't find any way of correcting it. $\endgroup$ May 10, 2015 at 16:49
  • $\begingroup$ @EngineerToast No, 1,000,000 = 499,999 + 500,001 $\endgroup$ May 10, 2015 at 16:50
  • $\begingroup$ @ghosts_in_the_code And that's why I usually don't post at night... Thank you for what should have been an obvious correction. $\endgroup$ May 11, 2015 at 13:21

A wordy explanation for the less mathematically inclined*

* warning: this problem is mathematical, numbers will be involved

The population of Barberland can be represented as a list of numbers.

A number can't appear on the list more than once, can't be greater than 1000000 or less than 0 (we'll assume than having a negative number of hairs is impossible but having zero is allowed), and no number in the list can be the sum of 2 other numbers in the list.

Zero can be included in any list without requiring any other numbers to be excluded because "Nobody in Barberland has the same number of hairs as the sum of two other inhabitants"

If we include the numbers 1 and 2 then the number 3 must be excluded. We could then include 4 but that would exclude 5 and 6. If we then included 7 that would exclude 8, 9 and 11. 10 would be okay to include (we don't have a pair of numbers that sum to 10) but that then excludes 11, 12, 14 and 17 because we have already selected 1,2,4 and 7.

This naive method of selecting numbers generates the Stöhr Sequence A033627 and results in approximately 1/3 of the numbers in a range being selected.

If we continue with this method of choosing numbers to include in the list, each one excludes more of the higher numbers. It really isn't a good way to approach the problem but does demonstrate the what happens if you try to include small numbers in the list.

By including 1 in the list you have effectively ruled out half of all possible numbers, as each other number you include would exclude 1 plus that number. If you were to start with 1 you could then pick only odd numbers all the way to 999999 because 2 odd numbers always sum to an even number.

Using only zero and odd numbers would result in a list of length 500001 (500000 odd numbers + 1 zero), approximately 1/2 of the numbers in the range being selected.

Working down from 1000000 is more effective. The sum of pairs of the largest numbers, are greater than 1000000, and so are not excluding any available options. This is true all the way down to 500000.

When we get to 499999 we can't include it without invalidating either 500000 or 999999. The smaller the number gets past 500000 the more larger numbers it invalidates in a way resembles the problems encountered when starting with small numbers.

Using the numbers zero and 500000 to 100000 results in a list of length 500002, slightly better than than the odd numbers method and significantly better than the naive method.


Nobody in Barberland has more than 1,000,000 hairs.

Well, no change here, population could be infinite.

No two inhabitants of Barberland have the same number of hairs.

Population maximum drops down to the count of [0,1,000,000], so 1,000,001

Nobody in Barberland has the same number of hairs as the sum of two other inhabitants' hairs.

Here is where life gets tricky. First off, we can exclude anyone below 500,000 as a means to capture the largest amount of data. This is because the sum of any two numbers in the set from [500,000,1,000,000] will be greater than 1,000,000 and eliminate that person from town. Thus we have 500,001.

But Wait, you say. What about the guy with no hair?

Good point for you to make. Since we require two different inhabitants, we can include the person with no hair. This is because we need to match the form Px + py = Pz where x =/= y =/= z to actively eliminate anyone. In the case of the bald person, x = y or y = z or x = z. That breaks the form and allows this person to remain in the city.
So our count is now 5,000,002.

But can we add anyone else?

Short answer, no. If you take the set from [500,000,1,000,000], you are assured to have nowhere that Px + Py = Pz where x =/= y =/= z. This means that none of these people would be eliminated from the city.
If you start adding people who are below the median value, you have to remove at least one person from your set.

  • $\begingroup$ How can you assure that [500,000, 1,000,000] is the optimal set? Ok, it's quite intuitive, but math things must be proven! $\endgroup$
    – leoll2
    May 11, 2015 at 19:53

I'm thinking along the lines of excluded numbers.

For any number you pick (n) after the first (f) you at minimum exclude one other number either Abs(f-n) where the sum is greater than the max (m), or f+n. therefore you can have Floor(m/2) + 1 plus the special case of 0 - giving us 500,002

reasoning for the minimum: As pointed out below you can exclude more than one number if you choose small numbers.

If you only choose Numbers greater than half the max (m) you are guarenteed to exclude only a single number because the sum of any two numbers greater than half max will be greater than max.

(m/2 + n1) + (m/2 +n2) = m + n1 + n2

  • 2
    $\begingroup$ Welcome to Puzzling SE! Your answer isn't very clear, could you add more details please? Thanks in advance! $\endgroup$
    – leoll2
    Apr 27, 2015 at 15:57
  • $\begingroup$ How do you insure that the third number doesn't prevent 2 numbers. Ie. if you have i,j and k selected why doesn't k cause both i+k and j+k to be impossible? $\endgroup$
    – Taemyr
    Apr 28, 2015 at 10:12

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