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. Threecups unsolvable.jpg
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. Threecupsproblem.jpg
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

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 top-selling puzzle game. It is widely considered to be the world's best-selling toy.

Tower of Hanoi Mathematical game or puzzle

The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

Dynamic programming method for solving a complex problem by breaking it down into a collection of simpler subproblems

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

Parity (mathematics) Property of being an even or odd number

In mathematics, parity is the property of an integer's inclusion in one of two categories: even or odd. An integer is even if it is divisible by two and odd if it is not even. For example, 6 is even because there is no remainder when dividing it by 2. By contrast, 3, 5, 7, 21 leave a remainder of 1 when divided by 2. Examples of even numbers include −4, 0, 82 and 178. In particular, zero is an even number. Some examples of odd numbers are −5, 3, 29, and 73.

Mechanical puzzle puzzle presented as a set of mechanically interlinked pieces

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 Ernő Rubik’s Cube that he invented 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 4x4x4 Rubiks cube variation

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 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 number game with 15 pieces but 16 spaces

The 15 puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8 puzzle. If the size is 3×3 tiles, the puzzle is called the 8 puzzle or 9 puzzle, and if 4×4 tiles, the puzzle is called the 15 puzzle or 16 puzzle named, respectively, for the number of tiles and the number of spaces. The goal of the puzzle is to place the tiles in order by making sliding moves that use the empty space.

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. 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 dodecahedral 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 brain teaser, puzzle, or paradox in logic, probability, and recreational 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. 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 featuring a loop which must be disentangled from a sequence of rings on interlinked pillars

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

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

Dino Cube combination puzzle

The Dino Cube is a cubic twisty puzzle in the style of the Rubik's Cube. It was invented in 1985 by Robert Webb, however it was not mass-produced until ten years later. It has a total of 12 external movable pieces to rearrange, compared to 20 movable pieces on the Rubik's Cube.

References

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

See also