#133 The Game of Life、#136 Catching a Spy

[GoodVincentTu]

• this is for 2nd sharing

#133. The Game of Life
This solitaire game is “played” on an infinite two-dimensional grid of square cells. Each of the cells is always in one of two possible states: live or dead. After some initial configuration of live cells is selected— for example, by marking them with a black dot—a sequence of new
65 Puzzles
configurations called “generations” is obtained by the following rules, which are applied simultaneously to every cell in the current generation. Every cell interacts with its eight neighbors, which are the cells that are adjacent to it horizontally, vertically, or diagonally. At each step in time, the following transitions occur:
(i) Death by underpopulation Any live cell with fewer than two live neighbors dies.
(ii) Death by overcrowding Any live cell with more than three live neighbors dies.
(iii) Survival Any live cell with two or three live neighbors lives on to
the next generation.
(iv) Birth Any dead cell with exactly three live neighbors becomes the
live cell.
(a) Find the smallest initial configuration of live cells that will remain the same with every generation. (Such configurations are called “still lifes.”)
(b) Find the smallest initial configuration of live cells that will oscillate between two states. (Such configurations are called “oscillators.”)
(c) Find the smallest initial configuration of live cells that will move across the board. (Such configurations are called “spaceships.”)

#136. Catching a Spy
In a computer game, a spy is located on a one-dimensional line. At time 0, the spy is at the location a. With each time interval, the spy moves b units to the right if b ≥ 0, and |b| units to the left if b < 0. Both a and b are fixed integers, but they are unknown to you. Your goal is to identify the spy’s location by asking at each time interval (starting at time 0) whether the spy is currently at some location of your choosing. For example, you can ask whether the spy is currently at location 19, to which you will receive a truthful yes/no answer. If the answer is “yes,” you reach your goal; if the answer is “no,” you can ask the next time whether the spy is at the same or another location of your choice. Devise an algorithm that will find the spy after a finite number questions.