Answer:
No-one gets out for 44 days after the governor's speech. On the 45th day, all the prisoners with green ink apply to be released, and are released. On the 46th day, all the prisoners with blue ink apply to be released and are released.
Explanation:
I think it's best to look at what would happen with smaller numbers of prisoners. And to do that, we'll pretend to be one of the prisoners - so we don't initially know our ink colour. I'm going to assume I can see the same or more blue than green. This is just to make the language less convoluted. The problem is obviously symmetric and works just as well with the colours all swapped.
First Case (two or more prisoners). All the other prisoners I can see have blue ink. I don't know my colour. The governor says that there are both colours. I immediately know I must be green, and apply for release the next day. The other prisoners apply the next day, as I can only have applied for release if I could see only one colour, which means they now all know that they are all blue.
Second Case (three or more prisoners): I can see one green and one or more blue prisoners. So you would think that the governor's statement doesn't help me, as I already know that there are both blue and green prisoners. But I can now reason as follows:
* If I am blue, the green prisoner can only see blue prisoners, so he will apply to be released tomorrow, as the governor's speech has told him that there are both colours present. This will confirm I'm blue and I can apply the following day.
* If the green prisoner I can see does not apply for release tomorrow, he must be able to see another green prisoner, which must be me. I must be green, and I can apply for release on the second day after the governor's speech.
Third Case (five or more prisoners): I can see two greens and two or more blues. This is an interesting case to consider, as I now know that all the other prisoners know that there are blue and green prisoners in the prison. However:
* If I am blue, each green prisoner can only see one other green prisoner. By the reasoning in the Second Case, they will both apply to be released on the second day after the governor's speech. This will confirm that I'm blue and I can apply to be released on the third day.
* If the two green prisoners I can see do not apply for release on the second day after the governor's speech, they must be able to see another green prisoner, which must be me. I must be green, and I can apply for release on the third day after the governor's speech.
Fourth Case (seven or more prisoners): I can see three greens and three or more blues.
* If I am blue, each green prisoner can see two other green prisoners. By the reasoning in the Third Case, they will all apply to be released on the third day after the governor's speech. This will confirm that I'm blue and I can apply to be released the fourth day.
* If the three green prisoners I can see do not apply for release on the third day after the governor's speech, they must be able to see another green prisoner, which must be me. I must be green, and I can apply for release on the fourth day after the governor's speech.
I think it's now obvious that this line of reasoning can be continued forever. Leading to the answer I gave above.
So what information has the governor given me with his speech?
1. He's given me the information that both colours are present in the prison. This allows me to get released in the First case.
2. He's given me the information that all the prisoners know that both colours are present in the prison (by telling us all when we're all gathered together). This allows me to do the reasoning to get released in the Second Case.
3. He's given me the information that all the prisoners know that all the other prisoners know that both colours are present in the prison. This allows me to do the reasoning in the Third Case.
4. He's given me the information that all the prisoners know that all the other prisioners know that all the other prisoners know that both colours are present in the prison. This allows me to do the reasoning in the Fourth Case.
And so on.... He's given me the information that it's valid to reason about what the other prisoners can reason about what the other prisoners can reson about..... etc. Which allows the chain of reasoning for the 45th Case to work.
Not convinced? Let me write out the Fourth Case in full, rather than refer to the earlier reasoning.
Fourth Case (seven or more prisoners): I can see three greens and three or more blues.
* If I am blue, each green prisoner I can see two green prisoners. Each of the three green prisoners I can see will reason as follows:
* If I am blue, each green prisoner I can see can only see one green prisoner. Each of the two green prisoners I can see will each reason as follows:
* If I am blue, the one green prisoner I can see can only see blue prisoners, and will reason as follows:
* I can only see blue prisoners and the governor's just said that there are blue and green prisoners. I can apply for release tomorrow, as I must be green.
I can then apply for release on the second day.
* If the one green prisoner I can see doesn't leave, there must be another green prisoner which that prisoner can see, which must be me. We'll both leave on the second day.
Of course, I can see two green prisoners, so I know that no-one will leave on the first day. But if the two green prisoners I can see leave on the second day, I must be blue and can leave on the third day.
* If the two green prisoners I can see don't leave on the second day, there must be another green prisoner which they can both see, which must be me. All three of us can leave on the third day
Of course, I can see three green prisoners, so I know that no-one will leave on the first or second days. But if the three green prisoners I can see leave on the third day, I must be blue and can leave on the fourth day.
* If the three green prisoners I can see don't apply to leave on the third day, there must be another green prisoner that they can all see, and it must be me. We can all apply to leave on the fourth day.
This is an case of Common Knowledge. When a fact is Common Knowledge, it isn't just known to all members of the group, but all members of the group know that all other members of the group know the fact, and also that all members of the group know that all members of the group know that all members of the group know the fact, etc.
Because the governor's speech has made the presence of both colours Common Knowledge amoung the prisoners, each prisoner can make a chain of assumptions about what the green prisoners that they can see can themselves see and can know, which leads to them to deduce their ink colour depending on whether the n green prisoners they can see leave the prison on the nth day after the speech.
The end of the chain of reasoning depends on the information from the governors speech. Without the governor having given the speech to them all, the chain of reasoning would break. What the governor's speech has done has been to convert the fact that there are both colours in the prison from a fact known to all the prisoners to a Common Knowledge fact.