Three cups problem

Last updated
The standard, unsolvable, arrangement of the three cups. Here, cups A and C are upright and B is upside down. Three cups problem unsolvable.svg
The standard, unsolvable, arrangement of the three cups. Here, cups A and C are upright and B is upside down.
The solvable version of the problem. Here, cups A and C are upside down, and cup B is upright. Three cups problem solvable.svg
The solvable version of the problem. Here, cups A and C are upside down, and cup B is upright.

The three cups problem, also known as the three cup challenge and other variants, is a mathematical puzzle that, in its most common form, cannot be solved.

Contents

In the beginning position of the problem, one cup is upside-down and the other two are right-side up. The objective is to turn all cups right-side up in no more than six moves, turning over exactly two cups at each move.

The solvable (but trivial) version of this puzzle begins with one cup right-side up and two cups upside-down. To solve the puzzle in a single move, turn up the two cups that are upside down — after which all three cups are facing up. As a magic trick, a magician can perform the solvable version in a convoluted way, and then ask an audience member to solve the unsolvable version. [1]

Proof of impossibility

To see that the problem is insolvable (when starting with just one cup upside down), it suffices to concentrate on the number of cups the wrong way up. Denoting this number by , the goal of the problem is to change from 1 to 0, i.e. by . The problem is insoluble because any move changes by an even number. Since a move inverts two cups and each inversion changes by (if the cup was the right way up) or (otherwise), a move changes by the sum of two odd numbers, which is even, completing the proof.

Another way of looking is that, at the start, 2 cups are in the "right" orientation and 1 is "wrong". Changing 1 right cup and 1 wrong cup, the situation remains the same. Changing 2 right cups results in a situation with 3 wrong cups, after which the next move restores the original status of 1 wrong cup. Thus, any number of moves results in a situation either with 3 wrongs or with 1 wrong, and never with 0 wrongs.

More generally, this argument shows that for any number of cups, it is impossible to reduce to 0 if it is initially odd. On the other hand, if is even, inverting cups two at a time will eventually result in equaling 0.

See also

Related Research Articles

Eight queens puzzle Mathematical problem set on a chessboard

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n = 2 and n = 3.

Rubiks Cube 3-D combination puzzle

The Rubik's Cube is a 3-D combination puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the Magic Cube, the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 via businessman Tibor Laczi and Seven Towns founder Tom Kremer. Rubik's Cube won the 1980 German Game of the Year special award for Best Puzzle. As of January 2009, 350 million cubes had been sold worldwide, making it the world's bestselling puzzle game and bestselling toy.

Magic square Sums of each row, column, and main diagonals are equal

In recreational mathematics, a square array of numbers, usually positive integers, is called a magic square if the sums of the numbers in each row, each column, and both main diagonals are the same. The order of the magic square is the number of integers along one side (n), and the constant sum is called the magic constant. If the array includes just the positive integers , the magic square is said to be normal. Some authors take magic square to mean normal magic square.

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

Tower of Hanoi Mathematical game or puzzle

The Tower of Hanoi is a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to the last rod, obeying the following rules:

  1. Only one disk may be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  3. No disk may be placed on top of a disk that is smaller than it.
Three utilities problem Mathematical problem

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity can be stated as follows:

Suppose three houses each need to be connected to the water, gas, and electricity companies, with a separate line from each house to each company. Is there a way to make all nine connections without any of the lines crossing each other?

Mechanical puzzle mechanically-interlinked pieces to be manipulated

A mechanical puzzle is a puzzle presented as a set of mechanically interlinked pieces in which the solution is to manipulate the whole object or parts of it. One of the most well-known mechanical puzzles is the Rubik's Cube, invented by the Hungarian architect Ernő Rubik in 1974. The puzzles are mostly designed for a single player where the goal is for the player to see through the principle of the object, not so much that they accidentally come up with the right solution through trial and error. With this in mind, they are often used as an intelligence test or in problem solving training.

Rubiks Revenge

The Rubik's Revenge is a 4×4×4 version of Rubik's Cube. It was released in 1981. Invented by Péter Sebestény, the Rubik's Revenge was nearly called the Sebestény Cube until a somewhat last-minute decision changed the puzzle's name to attract fans of the original Rubik's Cube. Unlike the original puzzle, it has no fixed facets: the centre facets are free to move to different positions.

Rubiks Magic Mechanical puzzle created by Erno Rubik

Rubik's Magic, like Rubik's Cube, is a mechanical puzzle invented by Ernő Rubik and first manufactured by Matchbox in the mid-1980s.

15 puzzle Sliding puzzle with fifteen pieces and one space

The 15 puzzle is a sliding puzzle having 15 square tiles numbered 1–15 in a frame that is 4 tiles high and 4 tiles wide, leaving one unoccupied tile position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in numerical order.

Megaminx Puzzle

The Megaminx or Mégaminx is a dodecahedron-shaped puzzle similar to the Rubik's Cube. It has a total of 50 movable pieces to rearrange, compared to the 20 movable pieces of the Rubik's Cube.

Induction puzzles are logic puzzles, which are examples of multi-agent reasoning, where the solution evolves along with the principle of induction.

Two envelopes problem

The two envelopes problem, also known as the exchange paradox, is a brain teaser, puzzle, or paradox in logic, probability, and recreational mathematics. It is of special interest in decision theory, and for the Bayesian interpretation of probability theory. Historically, it arose as a variant of the necktie paradox. The problem typically is introduced by formulating a hypothetical challenge of the following type:

You are given two indistinguishable envelopes, each containing money. One contains twice as much as the other. You may pick one envelope and keep the money it contains. Having chosen an envelope at will, but before inspecting it, you are given the chance to switch envelopes. Should you switch?

Baguenaudier Disentanglement puzzle

Baguenaudier, also known as the Chinese rings, Cardan's suspension, Cardano's rings, Devil's needle or five pillars puzzle, is a disentanglement puzzle featuring a loop which must be disentangled from a sequence of rings on interlinked pillars. The loop can be either string or a rigid structure.

God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any algorithm which produces a solution having the fewest possible moves, the idea being that only an omniscient being would know an optimal step from any given configuration.

Balance puzzle

A balance puzzle or weighing puzzle is a logic puzzle about balancing items—often coins—to determine which holds a different value, by using balance scales a limited number of times. These differ from puzzles that assign weights to items, in that only the relative mass of these items is relevant.

Impossiball

The Impossiball is a rounded icosahedral puzzle similar to the Rubik's Cube. It has a total of 20 movable pieces to rearrange, which is the same as the Rubik's Cube, but all of the Impossiball's pieces are corners, like the Pocket Cube.

The original Rubik's cube was a mechanical 3×3×3 cube puzzle invented in 1974 by the Hungarian sculptor and professor of architecture Ernő Rubik. Extensions of the Rubik's cube have been around for a long time and come in both hardware and software forms. The major extension have been the availability of cubes of larger size and the availability of the more complex cubes with marked centres. The properties of Rubik’s family cubes of any size together with some special attention to software cubes is the main focus of this article. Many properties are mathematical in nature and are functions of the cube size variable.

The monkey and the coconuts Diophantine mathematical puzzle

The monkey and the coconuts is a mathematical puzzle in the field of Diophantine analysis that originated in a magazine fictional short story involving five sailors and a monkey on a desert island who divide up a pile of coconuts; the problem is to find the number of coconuts in the original pile. The problem is notorious for its confounding difficulty to unsophisticated puzzle solvers, though with the proper mathematical approach, the solution is trivial. The problem has become a staple in recreational mathematics collections.

References

  1. Lane, Mike (2012). Close-Up Magic. The Rosen Publishing Group, Inc. ISBN   9781615335152.

See also