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

Related Research Articles

Diophantine equation Polynomial equation whose integer solutions are sought

In mathematics, a Diophantine equation is a polynomial equation, usually involving two or more unknowns, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

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. There are 92 solutions. The problem was first posed in the mid-19th century. In the modern era, it is often used as an example problem for various computer programming techniques.

Rubiks Cube 3-D combination puzzle

The Rubik's Cube is a 3-D combination puzzle originally 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. The cube was released internationally in 1980 and became one of the most recognized icons in popular culture. It 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 puzzle of avoiding crossings

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

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.

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way.

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.

Verbal arithmetic, also known as alphametics, cryptarithmetic, cryptarithm or word addition, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters of the alphabet. The goal is to identify the value of each letter. The name can be extended to puzzles that use non-alphabetic symbols instead of letters.

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.

Two envelopes problem Puzzle in logic and mathematics

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. It is a variant of an older problem known as the necktie paradox. The problem is typically introduced by formulating a hypothetical challenge like the following example:

Imagine you are given two identical 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 allusion to the Deity is based on an assumption that only an omniscient being would know an optimal step from any given configuration.

Five room puzzle Impossible puzzle in graph theory

This classical, popular puzzle involves a large rectangle divided into five "rooms". The objective of the puzzle is to cross each "wall" of the diagram with a continuous line only once.

Balance puzzle Logic 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.

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