I was able to think this through by an inductive argument. Here’s how I thought about it:
If you are the only person with blue eyes, you leave night 1 when you see no one else with blue eyes. I’ll call this the “Algorithm for 1 Blue-Eyed Person”.
Say that you have blue eyes and you see only one other person with blue eyes. You expect them to use the “Algorithm for 1 Blue-Eyed Person”, but they don’t leave night 1. The only way the algorithm would fail is if you yourself also has blue eyes, so you would both leave night 2. This is now the “Algorithm for 2 Blue-Eyed People”.
Now say there are three blue-eyed people, including you. You look at the other two blue-eyed people and expect them to do the “Algorithm for 2 Blue-Eyed People” and leave on night 2. But they don’t use the algorithm, which would only happen if you had blue eyes as well. So this becomes the next algorithm… etc.
In a group with 100 blue eyes, each of them see 99 other blue eyes and expect them to do the “Algorithm for 99 Blue-Eyed People” and leave by night 99, which doesn’t happen so you all leave on night 100.
Though the hardest part is getting an intuition about why the “algorithm 1” “algorithm 2” thinking happens at all when they’s a group of 100 people and everyone can see at least 99 blue eyed people. I get the induction, but why does anyone think ‘well algorithm 1 people would leave first night’ when there obviously can’t be anyone in this group. The only immediate question on everyone’s mind is “are there 99 blue eyed people (what I see) or 100 (me included)?”
I was able to think this through by an inductive argument. Here’s how I thought about it:
If you are the only person with blue eyes, you leave night 1 when you see no one else with blue eyes. I’ll call this the “Algorithm for 1 Blue-Eyed Person”.
Say that you have blue eyes and you see only one other person with blue eyes. You expect them to use the “Algorithm for 1 Blue-Eyed Person”, but they don’t leave night 1. The only way the algorithm would fail is if you yourself also has blue eyes, so you would both leave night 2. This is now the “Algorithm for 2 Blue-Eyed People”.
Now say there are three blue-eyed people, including you. You look at the other two blue-eyed people and expect them to do the “Algorithm for 2 Blue-Eyed People” and leave on night 2. But they don’t use the algorithm, which would only happen if you had blue eyes as well. So this becomes the next algorithm… etc.
In a group with 100 blue eyes, each of them see 99 other blue eyes and expect them to do the “Algorithm for 99 Blue-Eyed People” and leave by night 99, which doesn’t happen so you all leave on night 100.
Thanks. Yes, I’m managing to absorb it now.
Though the hardest part is getting an intuition about why the “algorithm 1” “algorithm 2” thinking happens at all when they’s a group of 100 people and everyone can see at least 99 blue eyed people. I get the induction, but why does anyone think ‘well algorithm 1 people would leave first night’ when there obviously can’t be anyone in this group. The only immediate question on everyone’s mind is “are there 99 blue eyed people (what I see) or 100 (me included)?”