The Barberland Institute of Trichodemographic Research has published the following results:
What is the maximum population of Barberland? Please, explain why.
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.
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.
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!
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.
* 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.
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
