Infected Chessboard
Source: Puzzle Toad, CMU
Problem: Gridville is a perfect city. It is laid out as an nXn grid and each of n^2 families inhabits its own square. A developer o ers to buy k < n plots at a price of one billion Wazooli's per plot. If a plot is bought, the family will move out and the plot will be used for growing Garbash, the most valuable commodity in GridWorld. If at any time, a family plot has two Garbash plots adjacent to it, the smell of the Garbash will cause them to leave and the developer will buy up the plot for a mere million Wazooli's and start growing Garbash. After, 10 years, the developer agrees to clean up and replace the plots by family homes, unless everybody has left.
The developer will not disclose where he plans to put his k initial plots.
Should the inhabitants of Gridville take the money, given that they want to gt
back to normal in 10 years?
Different version of the problem:
Source: Peter Winkler book "Mathematical Puzzles: A Connoisseur's Collection"
Problem: An infection spreads among the squares of an nXn checkerboard in the following manner. If a square has two or more infected neighbours, it becomes infected itself. (Each square has 4 neighbours only!). Prove that you cannot infect the whole board if you begin with fewer than n infected squares.
A different version mailed to me by Nikhil Garg (Sophomore, IIT Delhi) a few days back.
P.S. : 4th year 2nd sem rocks! Infi time for infi puzzles :P
Update (10/01/10): Solution: Posted by Nikhil Garg (Sophomore, IIT Delhi) in comments!!
Problem: Gridville is a perfect city. It is laid out as an nXn grid and each of n^2 families inhabits its own square. A developer o ers to buy k < n plots at a price of one billion Wazooli's per plot. If a plot is bought, the family will move out and the plot will be used for growing Garbash, the most valuable commodity in GridWorld. If at any time, a family plot has two Garbash plots adjacent to it, the smell of the Garbash will cause them to leave and the developer will buy up the plot for a mere million Wazooli's and start growing Garbash. After, 10 years, the developer agrees to clean up and replace the plots by family homes, unless everybody has left.
The developer will not disclose where he plans to put his k initial plots.
Should the inhabitants of Gridville take the money, given that they want to gt
back to normal in 10 years?
Different version of the problem:
Source: Peter Winkler book "Mathematical Puzzles: A Connoisseur's Collection"
Problem: An infection spreads among the squares of an nXn checkerboard in the following manner. If a square has two or more infected neighbours, it becomes infected itself. (Each square has 4 neighbours only!). Prove that you cannot infect the whole board if you begin with fewer than n infected squares.
A different version mailed to me by Nikhil Garg (Sophomore, IIT Delhi) a few days back.
P.S. : 4th year 2nd sem rocks! Infi time for infi puzzles :P
Update (10/01/10): Solution: Posted by Nikhil Garg (Sophomore, IIT Delhi) in comments!!
Its a classical invariant problem.
ReplyDeletePerimeter of infected area cant increase. It stays constant or decreases. Initially maxm perimeter is 4*k if k blocks are infected. If all blocks get infected perimeter becomes 4*n which is larger then 4*k (k <n) . So never would all square become infected.
Nice solution.. Thanx
ReplyDelete