skeptical scientist wrote:
Peeling wrote:It is common knowledge amongst the inhabitants that in order to infer their eye colour from the date of their arrival at the ferry, each individual would need to choose the same encoding schema.
Personally, I think picking the smallest possible 'base' for the number of islanders and ordering the code smallest to largest is the most efficient. No other optimisations are possible for the same reasons no optimisation of the official solution is possible: the same solution must work for every possible nested hypothetical.
Assuming I'm wrong, however, the perfect logicians on the island would know what the most efficient schema is.
On the offchance that there is more than one equally 'most efficient' schema (which I doubt), it would be common knowledge that neither schema is useful because there would be no way of knowing which another inhabitant would choose.
Therefore, they would choose the schema that is as efficient as possible whilst not being as efficient as any other schema.
Yeah, this doesn't work.
Pick any encoding scheme, choose two encodable pieces of information a and b, and swap the codes for a and b. You get a new, different encoding scheme which is equally efficient. So there is no unique most efficient encoding, and every schema is as efficient as some different schema, so there is no way to get uniqueness out of this without some communication to agree on a scheme.
That would be true if we were talking about the compression efficiency
of the code. For instance, if we were talking about assigning a number to each of fifty different English words, yes, there are many equally efficient schema and no way to pick the best.
But that's not what we're doing. In this case the compression efficiency of the code is fixed because of the nested hypotheticals of each individual. Efficiency in this case means picking the smallest number we know will uniquely represent what we're seeing. I've actually thought of a couple of optimisations, which I'll detail below.
As I mentioned, it's common knowledge that everyone's nested hypotheticals include every possible combination of eye colour. So for (say) 100 total inhabitants everyone knows that someone could think that someone could think that <etc> someone could see 99 of any given colour. So the minimum safe 'space' to allocate in the code for each visible eye colour is two decimal digits. However, it's also common knowledge that the smallest possible code number is 99. Why? Because anyone who could see less than 99 of one colour must
be able to see some of another colour too, making their code more than two decimal digits long. Given any number of eye colours, it's trivially obvious that the smallest number you can generate by thus encoding them is by arranging them smallest to largest.
Take a simpler example with just 10 people, where there are five green eyed, 3 blue eyed and two brown.
Everyone knows someone could think that <etc> someone could see 9 of any colour. So everyone knows they need to reserve one decimal digit per visible colour to ensure their code is unique to people sharing their eye colour (or who are an equal-sized group of eye colours, as dealt with in my original post). They also know they can subtract 9, because 9 is the smallest possible code anyone could come up with.
Greens see two brown, three blue and four green. The most efficient encoding for them is therefore 234 - 9 = 225.
Blues see two browns, two blues and five greens, making 225 - 9 = 216.
Browns see one brown, three blues and five greens, making 135 - 9 = 126.
Both browns go to the ferry on day 126, at which point everyone knows it's more efficient to re-evaluate than to stick with their original count (since it's common knowledge that an entire colour has just left the island, reducing everyone's visible eye colours, and thus the digits in their codes, by one).
So now there are just 8 people, making the code base 8 and the number to subtract, 7.
Greens see three blue and four green: (3*8)+(4)-7 = 21
Blues see two blue and five green: (2*8)+(5) - 7 = 14
The blues leave 14 days later. Now the base is 5 and the number to subtract, four.
Greens see four greens: (4)-4 = 0.
So all the greens go down the next day and leave. (This works because if any of them had had a different colour eye, the others would have seen 1X 3G, which encodes as (1*5)+3 - 4 = 4)
I can't think of any further safe optimisations. But if there are any, the people on the island would make them EDIT: Actually, I can think of a further optimisation - a rather significant one.
For ten people, nobody can generate a code value smaller than nine. We also know that the largest possible code number is 111111111, where someone sees nine individual eye colours.
That got me thinking: the sum of each group of digits in the code (in the case of ten people, a 'group' is a single digit) must equal 9. So in the example above:
Greens see 2,3,4 (total of digits is 9)
Blues see 2,2,5 (total of digits is 9)
Browns see 1,3,5 (total of digits is 9)
Therefore, we only need to consider codes where the digits add up to nine (for 100 people, it would be codes where adding up all the adjacent pairs of digits gets you to 99, eg: 99,0198,0297,0396 etc)
Thus rather than waiting for 126 days, the two browns would be able to work out which, in the ascending series of possible codes, was the index of theirs:
Greens see two brown, three blue and four green. The first-pass encoding for them is therefore 234.
Blues see two browns, two blues and five greens, making 225.
Browns see one brown, three blues and five greens, making 135.
1A 1B 3C 4D
Based on the common knowledge that all codes must have digits that sum to 9, and the digits will always be in ascending order, we can write those codes down as follows:
So the browns can go down on day 8. After that:
Green sees 3 blue 4 green, so first-pass code is (in base 8 ) 34
Blue sees 2 blue 5 green, so first-pass code is (in base 8 ) 25
Possible codes (in base 8 ) are 7,16,25
So blues leave 3 days later.
Green sees 4 green, so first pass code is (in base 5) 4
Possible codes in base 5 are 4
so greens leave next day.Problem:
This optimisation violates the need for uniqueness, because we are now mapping a each of a sparse list of code 'words' to a number, and there's no guarantee everyone would pick the same mapping.
I'm going to think a bit more about this, but I reckon that might be a fatal flaw in the optimised version.