25
$\begingroup$

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.

$\endgroup$
  • 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 '15 at 18:37
  • 3
    $\begingroup$ To the bounty: What strikes you as unrigorous about xnor's answer? $\endgroup$ – Milo Brandt May 7 '15 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 '15 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 '15 at 10:22
  • $\begingroup$ Should we assume that hair count is an integer value? $\endgroup$ – tfitzger May 11 '15 at 15:44
27
$\begingroup$

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.

$\endgroup$
  • 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 '15 at 11:17
  • $\begingroup$ ^ Lemme guess, one person is completely bald? $\endgroup$ – Joe Z. Apr 27 '15 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 '15 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$ – LogicianWithAHat May 7 '15 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 '15 at 15:41
15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ But why is that maximal? $\endgroup$ – reo katoa Apr 28 '15 at 2:00
7
+50
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ You are right, I was thinking about that myself,but you have posted it earlier than myself-only I forgot 0(bald). $\endgroup$ – Mathsman 100 May 7 '15 at 7:36
  • 3
    $\begingroup$ 500001 factorial? This answer is wrong! ;-)) $\endgroup$ – Rand al'Thor May 9 '15 at 8:16
  • 2
    $\begingroup$ That's not a factorial ahahahah! $\endgroup$ – leoll2 May 9 '15 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 '15 at 14:43
  • $\begingroup$ @GOTO0 You're right, I'll edit now. Thanks! $\endgroup$ – leoll2 May 13 '15 at 15:59
6
$\begingroup$

The answer is

500,002

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.

$\endgroup$
  • 10
    $\begingroup$ You can't have the person with 2 hairs unless you skip every other odd number. $\endgroup$ – Rob Watts Apr 27 '15 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$ – Engineer Toast May 8 '15 at 19:15
  • $\begingroup$ @RobWatts Yes, my answer is wrong and I can't find any way of correcting it. $\endgroup$ – ghosts_in_the_code May 10 '15 at 16:49
  • $\begingroup$ @EngineerToast No, 1,000,000 = 499,999 + 500,001 $\endgroup$ – ghosts_in_the_code May 10 '15 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$ – Engineer Toast May 11 '15 at 13:21
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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 '15 at 19:53
0
$\begingroup$

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

$\endgroup$
  • 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 '15 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 '15 at 10:12

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