There are 12 coins identical in appearance; either all are genuine or exactly one of them is fake. It is unknown whether the fake coin is lighter or heavier than the genuine one. You have a two-pan balance scale without weights. The problem is to find whether all the coins are genuine and, if not, to find the fake coin and establish whether it is lighter or heavier than the genuine ones. Design an algorithm to solve the problem in the minimum number of weighings.

• 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.

There are n glasses on the table, all standing upside down. In one move, you are allowed to turn over exactly n − 1 of them. Determine all values of n for which all the glasses can be turned up, and outline an algorithm that does this in the minimum number of moves.

You have n > 2 identical-looking coins and a two-pan balance scale with no weights. One of the coins is a fake, but you do not know whether it is lighter or heavier than the genuine coins, which all weigh the same. Design an algorithm to determine in the minimum number of weighings whether the fake coin is lighter or heavier than the others.

There are 12 very smart prisoners in a jail. To get rid of them, the warden
comes up with the following test. He will put a hat, either black or white,
on the head of each of these prisoners. There will be at least one hat of each
color, and the prisoners will be informed about this fact. They will be able
to see everyone else’s hat but their own; there will be no communications
of any kind among the prisoners. The warden will line up the prisoners
every 5 minutes starting at 12:05 pm and ending at 12:55 pm. To pass the
test, all the prisoners with a black hat and only those prisoners will have to
step forward during the same line up. If they do, all the prisoners will be
freed, otherwise they will be executed. How can the prisoners pass the test?

There are five items of different weights and a two-pan balance scale with no weights. Order the items in increasing order of their weights, making no more than seven weighings.

Consider the problem of placing n queens on an n × n chessboard so
that no two queens are in the same row, column, or diagonal. Design a
linear-time algorithm for finding a solution to this problem for any n > 3.

McNuggetNumbers
A McNugget number is a positive integer that can be obtained by adding together orders of McDonald’s Chicken McNuggets, which come in boxes of 4, 6, 9, and 20 pieces.
(a) FindallthepositiveintegersthatarenotMcNuggetnumbers.
(b) Designanalgorithmtocomputethenumberofboxesofeachorder
size for any given McNugget number.

Four people need to cross a rickety footbridge; they all begin on the same
side. It is dark, and they have one flashlight. A maximum of two people
can cross the bridge at one time. Any party that crosses, either one or two
people, must have the flashlight with them. The flashlight must be walked
back and forth; it cannot be thrown, for example. Person 1 takes 1 minute
to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes,
and person 4 takes 10 minutes. A pair must walk together at the rate of the
slower person’s pace. For example, if person 1 and person 4 walk together,
it will take them 10 minutes to get to the other side. If person 4 returns the
flashlight, a total of 20 minutes have passed. Can they cross the bridge in
17 minutes?

Three missionaries and three cannibals must cross a river. Their boat can only hold two people, and it cannot cross the river by itself with no people on board. Each missionary and each cannibal can row the boat. If present, missionaries cannot be outnumbered by cannibals. How can all six get across the river with the fewest crossings?

CrossingDots
Given an n × n point lattice (intersection points of n consecutive horizontal and n consecutive vertical lines on common graph paper), where n > 2, cross out all the points by 2n − 2 straight lines without lifting your pen from the paper. You may cross the same point more than once, but you cannot redraw any portion of the same line. (A “greedy” solution for n = 4, shown in Figure 2.28, has seven lines instead of the six required by the puzzle.)

One hundred different numbers are written on 100 cards, one number per card. The cards are arranged in 10 rows and 10 columns, in increasing order in each row (left to right) and each column (top down). All the cards are turned faced down so that you cannot see the numbers written on them. Can you devise an algorithm to determine whether a given number is written on one of the cards by turning up less than 20 cards?

英文

The object of this puzzle is to place the largest possible number of coins at points of the eight-pointed star depicted in Figure 2.9. The coins should be placed one after another, with the following restrictions: (i) a coin needs to be placed first on an unoccupied point and then moved along a line to another unoccupied point, and (ii) once a coin has been positioned in this manner, it cannot be moved again. For example, we can start by placing the first coin on point 6 and then moving it to point 1 (denoted 6 → 1), where the coin will have to remain. We can continue, say, with the following sequenceofmoves:7 → 2,8 → 3,7 → 4,8 → 5,whichplacesfivecoins.

中文

這個謎題的目標是在如圖2.9所示的八芒星的頂點上放置盡可能多的硬幣。硬幣必須一個一個放置，並遵守以下規定：

1. 硬幣必須先放在一個未被佔用的頂點上，然後沿著線移動到另一個未被佔用的頂點。
2. 一旦硬幣以上述方式就位後，就不能再移動

例如，我們可以在點6放第一枚硬幣，然後移動到 點1 (記做 6 -> 1)，這時應必將永遠留在 點1 上。繼續放置硬幣，假如以這樣的順序放置：7 -> 2，8 -> 3， 7 -> 4，8 -> 5，則最終會有5枚硬幣被放置在八芒星上。

Given an 8-pint jug full of water and two empty jugs of 5- and 3-pint capacity, get exactly 4 pints of water in one of the jugs by completely filling up and/or emptying jugs into others.

Problem 1
A man finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the man himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Show how the man can get all these “passengers” to the other side.

Problem 2
There are 20 gloves in a drawer: 5 pairs of black gloves, 3 pairs of brown, and 2 pairs of gray. You select the gloves in the dark and can check them only after a selection has been made. What is the smallest number of gloves you need to select to guarantee getting the following?
(a) Atleastonematchingpair
(b) Atleastonematchingpairofeachcolor

85. Rumor SpreadingI
    There are n people, each in possession of a different rumor. They want to share the news with each other by sending electronic messages. What is the minimum number of messages they need to send to guarantee that every one of them gets all the rumors? Assume that a sender includes all the rumors he or she knows at the time the message is sent and that a message may only have one addressee.
86. Rumor SpreadingII
    There are n people, each in possession of a different rumor. They want to share all the rumors through a series of bilateral conversations (e.g., via a telephone). Devise an efficient (in terms of the total number of conversations) algorithm for this task. Assume that in every conversation both parties exchange all the rumors they know at the time.

In a kindergarten, there are n children sitting in a circle facing their teacher
in the center. Each child initially has an even number of candy pieces.
When the teacher blows a whistle, each child simultaneously gives half of
his or her candy pieces to the neighbor on the left. Any child who ends up
with an odd number of pieces is given another piece by the teacher. Then
the teacher blows her whistle again, unless all the children have the same
number of candies, in which case the game stops. Can this game go on
forever or will it eventually stop to let the children go on with their lives?

There are eight disks of different sizes and four pegs. Initially, all the disks
are on the first peg in order of size, the largest on the bottom and the
smallest on the top. The objective is to transfer all the disks to another
peg by a sequence of moves. Only one disk can be moved at a time, and
it is forbidden to place a larger disk on top of a smaller one. Devise an
algorithm that solves the puzzle in 33 moves.

There are 10 stacks of 10 identical-looking coins. All of the coins in one of these stacks are counterfeit, and all the coins in the other stacks are genuine. Every genuine coin weighs 10 grams, and every fake weighs 11 grams. You have an analytical scale that can determine the exact weight of any number of coins. What is the minimum number of weighings needed to identify the stack with the fake coins?

A firm has invented a super-strong egg. For publicity purposes, it wants to determine the highest floor in a 100-story building from which such an egg can fall without breaking. The firm has given a tester two identical eggs to experiment with. Of course, the same egg can be dropped multiple times unless it breaks. What is the minimum number of droppings that is guaranteed to determine the highest safe floor in all cases?

There is a row of n checkers of three colors: red, white, and blue. Devise an algorithm to rearrange the checkers so that all the red checkers come first, all the white ones come next, and all the blue checkers come last. The only operations allowed are examination of a checker’s color and swap of two checkers. Try to minimize the number of swaps made by your algorithm.

On a one-dimensional board with 2n + 1 cells, there are n counters in the first n cells representing Toads and n counters in the last n cells representing Frogs. Toads and Frogs take turns moving. Moves consist of sliding a Toad or Frog into the empty cell or jumping over one opposing creature to the empty cell. (Toads cannot jump over themselves and neither can Frogs.) Toads can only move rightward; Frogs can only move leftward. The object is to make them switch their positions

Consider an equilateral triangle formed by closely packed pennies or other identical coins like the one shown in Figure 2.27. (The centers of the coins are assumed to be at the points of the equilateral triangular lattice.) Design an algorithm to flip the triangle upside down in the minimum number of moves if on each move you can slide one coin at a time to its new position. Give a compact formula for the number of minimum moves.

In a single-elimination tournament—such as the tennis Grand Slam
championships—every losing player is immediately eliminated from the
subsequent rounds of play until a single winner is determined. If such a
tournament starts with n players, determine the following:
(a) What is the total number of matches needed to get a winner?
(b) How many rounds are there in such a tournament?
(c) How many more matches need to be played to determine the secondbest
player based on the information produced by the tournament?

英文

There are n disks of different sizes and three pegs. Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top. The object is to transfer all the disks to the third peg. Only one disk can be moved at a time, and it is forbidden to place a larger disk on top of a smaller one. In addition, any move should either place a disk on the middle peg or move a disk from that peg (Figure 2.19). Design an algorithm that solves the puzzle in the minimum number of moves.

中文

有n個不同的小的盤子和3根柱子。最初，所有的盤子都按大小順序放置在第一根柱子上面，最大的在最下面，最小的在最上面。現在想要將所有的盤子都移動到第三根柱子上面去。一次只能移動一個盤子，而且禁止將大盤子放在小盤子上面。此外，每次移動要麽在中間柱子上面放置一個盤子，要麼從中間柱子上面取走一個盤子，如圖2.19所示，請設計一個演算法解決此問題，使得所使用的移動次數最小

提示

用遞迴解

There are eight identical-looking coins; one of these coins is counterfeit and is known to be lighter than the genuine coins. What is the minimum number of weighings needed to identify the fake coin with a two-pan balance scale without weights?

Given n > 1 items and a two-pan balance scale with no weights, determine the lightest and the heaviest items in ⌈3n/2⌉ − 2 weighings.

A researcher puts three types of chameleons on an island: 10 brown, 14 gray, and 15 black. When two chameleons of different colors meet, they both change their colors to the third one. Will it be possible for all the chameleons to become the same color?

A car odometer can display any six-digit combination from 000,000 to 999,999, inclusive. If it runs through its entire range, how many such combinations will have at least one digit 1 in them? What is the total
45 Puzzles
number of times the digit 1 will be displayed? (For example, 101,111 contributes five toward the total count of 1’s, and the next reading of 101,112 adds four more.)

英文

There are n pancakes, all of different sizes, that are stacked on top of each other. You are allowed to slip a spatula under one of the pancakes and flip over the whole stack above the spatula. The objective is to arrange the pancakes according to their size with the biggest at the bottom. Figure 2.20 shows an instance of the puzzle for n = 7. Design an algorithm for solving this puzzle and determine the number of flips made by the algorithm in the worst case.

中文

存在n個大小各異的煎餅，他們彼此重疊在一起。允許你用一個平底鏟，將平底鏟塞到其中一個煎餅底下，並把鏟子上面所有的煎餅都翻轉過來。我們的目標是把煎餅按大小順序排列ㄝ使得最大的在最下面，最小的在最上面。圖2.20顯示在n = 7 時該問題的一個例子。請設計一個演算法解決這個謎題，並且得出該演算法在最糟糕的情況下需要的翻轉次數。