There is a grid of prison cells of n cells by n cells, each cell holding a prisoner.

The prisoners want to plan a prison break which requires all the prisoners to act at once. They want to decide on a particular time for the breakout.

A group of r prisoners meet and decide on a time, where r. They then decide to spread the decided upon time by communicating with prisoners in neighboring cells--- prisoners in immediately close cells to the north, south, west, and east. However, a prisoner will believe the time only if he/she hears from one neighbor north/south and one neighbor east/west (e.g., a prisoner would believe the time if the neighbor north and the neighbor east tell him the time; but a prisoner would not believe the time if the neighbor north and the neighbor south pnly told him the time).<>

For example, if shaded cells denote the pisoners who know the time of revolt in the left picture below, then the set of people who know the secret time the next day is depicted by the picture on the right.

(In the above, there is a 4x4 prison grid, and every prisoner who has at least two neighbors, one to the north/south and the other to the east/west, that know the time gets to know the time, while others don't.)

Prove that for any n>1 and any r, no matter where these r prisoners are, and no matter how many days elapse, there will be at least one prisoner who does NOT know the time for revolt.<>

You need to prove (b) by induction formally.

Hint: Show that initially there is a particular set of prisoners that do not know the time, and then show that these prisoners will never get to know the time ever, by induction.