## The Witch Puzzle II (witches1)

The witch puzzle has been introduced in model witches. In this section, we show how to generate new witch puzzles.

The witch puzzle has been introduced in model witches. In this section, we show how to generate new witch puzzles.

This puzzle is an interesting pastime. Print out the 3×3 puzzle squares shown in Figure 1 on a color printer. Cut out the nine squares to place the 9 pieces on the table. The puzzle is simple: Arrange the pieces into a 3×3 square in such a way that the pieces matches up so that each “puz” front is matched up with the corresponding “zle” horizontally and vertically with the next piece. Good luck! Depending on the puzzle and how they are arranged, it’s quite a challenge. Great for a rainy day if your “Stop the Rain” spell doesn’t work! This puzzle is known as the “witch puzzle” because the pieces of some commercial games contain bitmaps of colored witches.

A number n of “umbrellas” (⊤) (2-dimensional spanned “umbrellas”) is given. Their heights can be modified arbitrarily. The problem is to push these umbrellas together as closely as possible such that the total span is as minimal as possible. A small example with four umbrellas is given in Figure 1 with their widths 6, 8, 11, and 22. The idea of this model is from Ivo Blöchliger.

Two players play the following number game: Each chooses (secretly) a positive number. The numbers are then uncovered at the same time and compared. If the numbers are equal, neither of the players will get a payoff. If the numbers differ by one, then the player who has chosen the higher number obtains the sum of both, otherwise the player with the smaller number obtains the smaller of both. The play is repeated endlessly. Which number and how often should a player choose a number in each round? (The game has been described in [1].)

A Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is the length of the ruler. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. A Golomb ruler of a given order with minimal length is called a optimal Golomb ruler.

The problem has been described in alcuin. Here a different formulation is presented.

“A man had to take a wolf, a goat and a bunch of cabbages across the river. The only boat he could find can only take the man and of them at a time. But he had been ordered to transfer all of these to the other side in good condition. How could this be done?”

Albert Einstein supposedly wrote this quiz. The puzzle is as follows:

This one-dimensional cellular automaton consists of n (here n = 20) cells arranged in a horizontal line with the leftmost being cell 0. Each cell i has two neighbors: a left one l(i) and a right one r(i). The left neighbor of cell 0 is cell n- 1, and the right neighbor of cell n- 1 is cell 0.