Computer Science

The Wolf, the Goat, and the Cabbage

A rural man wishes (for reasons that are not normally disclosed) to take a wolf, a goat and a cabbage across a broad river in a rowboat. The boat is very small, unfortunately, and the poor man has room in the boat for only one of these organisms at a time. What's worse, he cannot leave the wolf and the goat on the same bank, whether coming or going, for the wolf will surely eat the goat. Nor can he leave the goat and cabbage on the same bank because the goat will eat the cabbage. Is the feat even possible? If so, how does the man manage it?

Please show me the solution -- I give up

Word Magic

Invented by Lewis Carroll, this class of puzzles involves the transformation of one word into another by single-letter substitutions. The result is a form of magic, in which one thing is changed into another. For example, one can change a "cup" to a "rib" by the following sequence of substitutions: cup --> cap --> rap --> rip --> rib. Itıs not too difficult to change a "dog" into a "cat," but can you change "snow" into "rain?" Of course, every intervening word must be in your favorite dictionary.

Please show me the solution -- I give up

The Towers of Hanoi

Certain ancient Buddhist monks have declared that the world will end by the time a certain puzzle is completely solved. A number of golden discs of graded sizes, from small to large, reside upon a silver peg set in a thick sheet of hammered brass engraved with all manner of figures depicting Buddhist spirits and deities. The largest disc is at the bottom of this column and the smallest at the top. The intervening discs all get smaller, from bottom to top. Two other stout silver pegs have also been implanted in the brass base.

The solver of this puzzle must move all the discs from their present peg to one of the other pegs, but under the following ancient restrictions: a) only one disc at a time can be moved; b) a larger disc may never be placed upon a smaller one.

If there are seven discs, can you find a procedure for effecting the transfer? If you can complete one move a second, how long should it take you, at a minimum, to move all the discs?

As far as the Real Puzzle is concerned, in an obscure monkish cell somewhere in Benares an old man moves one of the 64 discs every second. (A younger man in the next cell waits patiently for the old one to die so that he may take over as Mover of the Discs.) Will the monks solve the puzzle before the world ends in 20 billion years?

Please show me the solution -- I give up

Desert Drums

A desert patrol vehicle has a 10-gallon tank and gets ten miles to the gallon no matter what load it carries. At the depot, there are two 50-gallon fuel drums. How far can the patrol vehicle travel before running out of gas if it can carry only one drum at a time?

The vehicle begins with a full tank of gas. It may drop off and pick up drums at will, traveling back and forth along its route, as necessary.

Please show me the solution -- I give up

Passing Trains

Owing to an administrative foul-up, two trains have been sent toward each other along the same stretch of track. Luckily, the engineers see each other in time to stop. Between the trains there is a small, abandoned siding that will hold an engine or just one car at a time. The siding is equipped with a switch at both ends.

Can you develop a procedure for getting the trains past each other using the tiny siding? You may assume that each train has five cars.

Please show me the solution -- I give up

The Flat Computer

Show that it is possible, in principle, to construct the logic for a general purpose computer entirely in the plane. Obviously the two-input logic gates OR and AND can be embedded in the plane, as can the inverter or negation gate, NOT.

It remains only to construct a crossover circuit in the plane. This circuit must consist of a planar configuration of the aforementioned gate types, the circuit having two inputs, A and B, as well as two outputs A' and B'. The output A' emerges on the opposite side of the circuit entered by A, and so with B' and B. (See the schematic below.) Simultaneously, whatever logic signal (0 or 1) enters either input, the same signal leaves the circuit on the corresponding output.

Note: The OR and AND gates each have to inputs, x and y. The output of the OR gate carries the signal x+y (logical). The output of the AND gate carries the signal x.y (logical). The NOT gate has one input x and one output x', where x' is the logical complement of x.

Please show me the solution -- I give up

Three Jugs of Wine

Two wine-lovers have, between them, an eight-quart jug of wine which they wish to share evenly. They also have an empty three-quart jar and an empty five-quart jar. How do they divide the wine into two equal (four-quart) portions?

Please show me the solution -- I give up

The Bad Penny

You have been handed twelve pennies by a philanthropist who believes one of them to be "bad," that is, either overweight or underweight. You may use only a balance to determine which penny is bad and whether it is overweight or underweight. What is the minimum number of weighings you need to make the determination? If you actually succeed in finding the number and demonstrating a procedure that requires only three weighings, the philanthropist will give you the eleven good pennies. (You were expecting gold?)

Please show me the solution -- I give up

de Bruijn Strings

You are given 16 bits, eight of them 1s and eight of them 0s. Arrange the bits in a sequence so that every possible four-bit number appears exactly once as a sequence of four consecutive bits.

Please show me the solution -- I give up

Wiring a House

A long hallway has a light in the middle that is controlled by a switch at either end. If someone turns the light off at one end, someone else may turn it on again at the other end. Each switch is of the double-throw type. In other words, in one position it closes one circuit, in the other position, it closes another.

Draw a circuit diagram for the two switches and the light.

Please show me the solution -- I give up

Twenty Questions

I am thinking of a number between 1 and 1,000,000. If you want to know what number I have in mind and are not clairvoyant, you may ask what the number is, but I won't make it easy for you.

Only questions with "yes" or "no" answers will be allowed. Can you find the mystery number by asking just 20 questions? What sort of question will you ask?

Please show me the solution -- I give up

Be A Memory Expert!

Someone is about to recite a list of 99 numbers between 1 and 100, inclusive. The numbers will be spoken in random order while you listen intently. You will listen intently because a) you can't take notes and b) you will be asked to name the missing number.

You have ten minutes to devise a method or algorithm that will enable you to state which of the numbers between 1 and 100 inclusive was omitted from the recitation.

Please show me the solution -- I give up

Round and Round She Goes: Where She Stops....

If you write a sequence of n positive integers in a directed circle, you may apply the following procedure to a number and its successor: Form the absolute difference of the two and replace the number by the result. Now the algorithm consists of applying the procedure to every number in the circle in turn, going around the circle as many times as necessary to produce a circle consisting entirely of zeros.

Show that if n = 4 the algorithm is guaranteed to terminate.

Is the same thing true for n = 5?

Please show me the solution -- I give up

The Fiendish Rotating Light bulb

A light bulb is wired in series to four pushbuttons located at the corners of a square base. The whole assembly, moreover, can be rotated through arbitrary angles. Two factors prevent you from turning the light bulb on immediately; First, the buttons are already in an unknown mixture of states, some on, some off. Second, every time you push a new combination of buttons in an effort to turn the light on, a fiend spins the assembly through an unknown multiples of 90 degrees. Thus, you have no idea exactly which buttons you pushed on the previous trial.

Is it possible to devise an algorithm that is guaranteed, eventually to turn the light bulb on? Indeed, such an algorithm exists. Moreover, it guarantees that the bulb will have been turned on by a fixed number of steps. All you have to do is find the algorithm. [Hint: Think parity.]

Please show me the solution -- I give up

Complementing a Matrix

One does not "complement" a binary matrix by admiring its entries, but by exchanging 0s and 1s throughout a given row or column. If one adds up the entries in a given column or row, the resulting number could be positive, negative, or zero. Devise a procedure that a) complements the matrix a certain number of times, b) ends when all rows and columns of the final product have nonnegative sums. (Hint: Is this puzzle as easy as it sounds?)

Please show me the solution -- I give up

The Spear Dance

It was quite a spectacle for nineteenth century explorer Stanley Livingston, as flames leapt into the night sky. Circling the central fire were n warriors carrying spears. Within their circle, n virtuous maidens also circled, each carrying a basket. Each participant in this strange dance carried spear or basket either hoisted aloft or held alow - beside the body.

Although Livingston was never able to discover the significance of the dance, the rule followed by the dancers was very simple; both circles would rotate in opposite directions until each warrior found himself opposite the next maiden. If a warrior who carried his spear aloft found himself opposite a maiden with her basket down, he would promptly give a shout, stamp his feet and lower his spear. She, meanwhile, would give a shout, stamp her feet and raise her basket overhead. The same thing happened if the spear were low and the basket aloft; each would switch the position of spear or basket.

Viewed as an arrangement of zeros (down) and ones (up), the pattern in either circle would change from one iteration to the next of this curious rule. But, just as obviously, sooner or later at least one of the patterns would have to repeat itself, as there are only a finite number of possibilities. What is the smallest number of iterations that guarantee this event, no matter what pattern is involved?

Please show me the solution -- I give up