Puzzle
7 minute read

Ponder This Challenge - November 2002 - 4 bottles on a square turntable

Ponder This Challenge:

This month's puzzle comes from David Gamarnik, who heard it after a wedding in the Republic of Georgia.
You are blindfolded. In front of you is a square turntable with four bottles at the corners. Each might be oriented "up" or "down". You make a sequence of "moves". Each move consists of five phases:
(1) A referee turns the table an unknown number of quarter-turns;
(2) You select "adjacent" or "opposite", and then take a pair of bottles which are either "adjacent" (90 degrees apart) or "opposite" (180), accordingly.
(3) You observe (by touch) the current orientation of these two bottles.
(4) You turn over one or the other bottle, or neither, or both.
(5) The referee tells you whether all four bottles are in the same orientation; if so, you win and the game is over.

After how many moves can you guarantee that you will have won?
What is your strategy?

Extra credit:
Prove that this is the minimum number of moves for which a guarantee can be made.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

  • Although we didn't realize it at the time, this month's puzzle was due to Martin Gardner, in the February 1979 issue of Scientific American.

    Five moves.

    We will denote positions of bottles as "U", "D" or "?", for "up", "down" or "unknown", respectively.
    We list the four positions clockwise, up to unknown rotation. Initially they are "? ? ? ?".

    First move: Take two opposite bottles and turn them "up".
    Now their setup is "? U ? U".

    Second move: Take two adjacent bottles and turn them "up".
    Now the setup is "? U U U".
    Assuming the referee does not stop the game, we know in fact that the setup is "D U U U".

    Third move: Take two opposite bottles.
    If one is "down", turn it "up", so that we win ("U U U U").
    Otherwise they are both "up"; turn one "down", so that we are left with "D D U U".

    Fourth move: Take two adjacent bottles and turn them over.
    If they were both "up", we win with "D D D D".
    If they were both "down", we win with "U U U U".
    Otherwise our setup becomes "D U D U".

    Fifth move: Take two opposite bottles and turn them over, winning.

    Why is four moves impossible?

    There are four non-winning positions (up to rotation):
    P1 = "U U U D",
    P2 = "D D D U",
    P3 = "U D U D",
    P4 = "U U D D".
    Suppose for the moment that we even know which position we are in.
    From P3 it requires one move to win.
    From P4 it requires two moves to guarantee a win;
    one move does not suffice, since whether we pick "opposite" or "adjacent"
    the two untouched bottles can have differing orientations.
    From P1 it requires three moves to guarantee a win:
    if we pick "opposite" we can be given two "up" bottles, and can
    only get to P2 or P1 or P4;
    if we pick "adjacent" we can be given two "up" bottles (and not
    know which ones), and no matter what we do, the referee can
    force us into P1 or P2 or P4.

    Return to the real game, in which we don't know whether we are starting with P1, P2, P3 or P4.
    On our first move, whether we select "adjacent" or "opposite", the referee will arrange for the two bottles we see to have differing orientations (one "up", one "down"), and no matter what we do at that point, we will be left with a set of possibilities that contains one of the sets {P1,P3} or {P1,P4} or {P2,P3} or {P2,P4}.
    (For example, if we choose "adjacent" and then change "UD" to "UU" we will be left with either P1 or P4, and not know which.)
    On our second move, no matter what we do, we will be left with a set of possibilities that includes P1 (or else it includes P2).
    Then even if the referee tells us our position, we still require three more moves to finish.

    If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

  • Vineet Gupta (11.01.2002@02:07:36PM EST)
  • Louis Slothouber (11.01.2002@04:04:37PM EST)
  • Stephen Martin (11.01.2002@05:27:10PM EST)
  • Michael Malak (11.01.2002@05:47:38PM EST)
  • Vladimir Sedach (11.01.2002@05:59:14PM EST)
  • Ross Millikan (11.01.2002@06:06:20PM EST)
  • Sriraman M Tallam (11.01.2002@06:53:32PM EST)
  • Mohan Rajagopalan (11.01.2002@06:53:32PM EST)
  • Dean M Starrett (11.01.2002@08:16:27PM EST)
  • Joseph DeVincentis (11.01.2002@08:33:42PM EST)
  • Wu Zheng (11.01.2002@08:57:07PM EST)
  • Frank Mullin (11.01.2002@10:06:19PM EST)
  • Shashidhar V (11.02.2002@01:13:18AM EST)
  • Arun Gautam (11.02.2002@07:31:40AM EST)
  • Manoj Kumar (11.02.2002@09:06:19AM EST)
  • Jonathan Wildstrom (11.02.2002@10:31:46AM EST)
  • Hazem D. Elmeleegy (11.02.2002@11:32:52AM EST)
  • William Heller (11.02.2002@03:07:52PM EST)
  • Vitaly Stakhovsky (11.02.2002@08:28:51PM EST)
  • Chetan Kamat (11.03.2002@01:11:45AM EST)
  • David P Woodruff (11.03.2002@01:59:49AM EST)
  • G V R Anand (11.03.2002@04:23:00AM EST)
  • Kozma Laszlo (11.03.2002@08:13:42AM EST)
  • Gil Better (11.03.2002@08:16:55AM EST)
  • Sarang Aravamuthan (11.03.2002@10:33:48AM EST)
  • Michael Brand (11.03.2002@11:56:17AM EST)
  • Matthew Martin (11.03.2002@01:48:14PM EST)
  • Jeffrey Lebak (11.03.2002@01:48:14PM EST)
  • John Ritson (11.03.2002@06:31:47PM EST)
  • (11.03.2002@06:31:47PM EST)
  • Vincent Lynch (11.03.2002@07:08:52PM EST)
  • (11.03.2002@07:08:52PM EST)
  • Anthony Coore (11.03.2002@11:11:13PM EST)
  • (11.03.2002@11:11:13PM EST)
  • Juraj Weisz (11.04.2002@03:51:57AM EST)
  • Dan Ungureanu (11.04.2002@03:54:58AM EST)
  • (11.04.2002@03:54:58AM EST)
  • Srihari Adireddy (11.04.2002@10:23:06AM EST)
  • (11.04.2002@10:23:06AM EST)
  • Tim Deegan (11.04.2002@11:21:29AM EST)
  • (11.04.2002@11:21:29AM EST)
  • Peter Huggins (11.04.2002@12:06:15AM EST)
  • (11.04.2002@12:06:15AM EST)
  • Francis Golding (11.04.2002@01:03:24PM EST)
  • (11.04.2002@01:03:24PM EST)
  • Yuvraj Singh Dhillon (11.04.2002@01:19:20PM EST)
  • (11.04.2002@01:19:20PM EST)
  • Karl D'Souza (11.04.2002@01:45:45PM EST)
  • (11.04.2002@01:45:45PM EST)
  • Michael Swart (11.04.2002@04:45:10PM EST)
  • (11.04.2002@04:45:10PM EST)
  • (11.04.2002@04:46:51PM EST)
  • Philippe J Sartori (11.04.2002@04:46:51PM EST)
  • (11.04.2002@04:46:51PM EST)
  • Christopher Howe (11.04.2002@05:19:33PM EST)
  • Michael P. Moyer (11.04.2002@08:37:06PM EST)
  • Ashish Mishra (11.04.2002@08:42:14PM EST)
  • Alex Wagner (11.04.2002@10:45:33PM EST)
  • Ravivrat Pandey (11.05.2002@02:01:00AM EST)
  • Gyora Benedek (11.05.2002@05:22:56AM EST)
  • Pedro (11.05.2002@07:46:56AM EST)
  • Dan Florescu (11.05.2002@08:53:18AM EST)
  • Cosmin Arad (11.05.2002@11:17:25PM EST)
  • Aleksandar Damnjanovic (11.05.2002@11:35:55AM EST)
  • Pascal Brisset (11.05.2002@12:59:03PM EST)
  • Sriram K. Rallabhandi (11.05.2002@04:45:00PM EST)
  • Jayavel Sounderpandian (11.05.2002@06:33:15PM EST)
  • Lavanya Kannan (11.05.2002@10:02:07PM EST)
  • Traian Dajma (11.06.2002@08:08:43AM EST)
  • Drahovsky Jozef (11.06.2002@08:55:42AM EST)
  • Alan O'Donnell (11.06.2002@11:02:53AM EST)
  • Dan Schwarz (11.06.2002@11:28:14AM EST)
  • Buckeye GSS (11.06.2002@12:23:45AM EST)
  • Shmuel Spiegel (11.06.2002@12:36:36AM EST)
  • Francois Galilee (11.06.2002@02:11:50PM EST)
  • Daniel A Clymer (11.06.2002@06:30:02PM EST)
  • Roger D Thompson (11.07.2002@05:58:54AM EST)
  • Peter Cervenanský (11.07.2002@08:30:52AM EST)
  • Tal Weiss (11.07.2002@11:52:03AM EST)
  • Joe Vanore (11.07.2002@02:29:52PM EST)
  • Kishore Gangwani (11.07.2002@05:58:18PM EST)
  • Sauraj Goswami (11.07.2002@06:59:36PM EST)
  • Ervan Darnell (11.08.2002@01:54:01AM EST)
  • Gaurav Bhalotia (11.08.2002@03:00:49AM EST)
  • Marko Vogrin (11.08.2002@02:56:45PM EST)
  • Ryan Mickler (11.08.2002@07:07:04AM EST)
  • Frans Buijsen (11.08.2002@10:07:11AM EST)
  • Will Jarvis (11.08.2002@11:52:00AM EST)
  • JP Sugarbroad (11.08.2002@03:13:42PM EST)
  • Ibrahim Okuyucu (11.09.2002@04:19:31AM EST)
  • Maxim G. Smith (11.09.2002@10:36:43AM EST)
  • Claudio Baiocchi (11.11.2002@04:00:02AM EST)
  • Rok Jamnik (11.11.2002@07:23:02AM EST)
  • Roger Duthie (11.11.2002@07:46:09AM EST)
  • Hagen von Eitzen (11.11.2002@07:59:02AM EST)
  • Frank (11.11.2002@10:33:06AM EST)
  • Suryaprasad Kareenahalli (11.11.2002@11:58:00AM EST)
  • Soonho you (11.11.2002@09:33:00 PM EST)
  • Grant Lammi (11.11.2002@11:26:07PM EST)
  • Chip Lynch (11.12.2002@02:08:05AM EST)
  • Cristian Mocanu (11.12.2002@03:33:34AM EST)
  • Nachiket Bapat (11.12.2002@05:06:02PM EST)
  • Stephen E. F. Villee (11.12.2002@10:20:15PM EST)
  • John G. Fletcher (11.13.2002@01:20:16AM EST)
  • Nick Jones (11.13.2002@12:00:46PM EST)
  • Narayanan Rajamani (11.13.2002@10:44:54PM EST)
  • Vivek Kumar Mehra (11.14.2002@07:39:38AM EST)
  • Mark Pilloff (11.14.2002@05:50:00PM EST)
  • Vivek Parashar (11.15.2002@07:37:00AM EST)
  • Suresh Ramakrishnan (11.15.2002@04:08:08PM EST)
  • Clive Tong (11.15.2002@04:15:57PM EST)
  • Hassan Masum (11.16.2002@10:49:45AM EST)
  • Daniel Wood (11.16.2002@12:01:02AM EST)
  • Nandakumar R. (11.17.2002@02:33:51AM EST)
  • Gaurav Agrawal (11.17.2002@05:26:40AM EST)
  • Itsik Horovitz (11.17.2002@06:52:55AM EST)
  • Mukul Madhukar Joshi (11.17.2002@10:36:04AM EST)
  • Suresh Ganesan (11.18.2002@04:54:44AM EST)
  • Ziga Hajdukovic (11.18.2002@06:41:05AM EST)
  • Colin Pinto (11.18.2002@10:33:19AM EST)
  • Peter Bennett (11.18.2002@10:34:00AM EST)
  • Daniel Bitin (11.18.2002@10:42:48AM EST)
  • Mrinalini T. Chaturvedi (11.18.2002@02:48:00PM EST)
  • Shriram Bharath (11.18.2002@06:22:00PM EST)
  • Mitchell A. Kaplan (11.18.2002@11:30:10PM EST)
  • Sameer Pawanekar (11.19.2002@07:49:00AM EST)
  • Stephane Higueret (11.19.2002@08:15:55AM EST)
  • Jan Rüten-Budde (11.19.2002@12:52:26PM EST)
  • Chris Shannon (11.19.2002@10:20:52PM EST)
  • Liu Jianjun (11.20.2002@12:33:06AM EST)
  • Gregory Dietrich (11.20.2002@04:26:58AM EST)
  • Christopher Yao (11.22.2002@06:51:22AM EST)
  • Andrew Rose (11.22.2002@09:57:19AM EST)
  • Nagendra (11.24.2002@11:49:15PM EST)
  • Pradeep S Bhatt (11.25.2002@08:05:40AM EST)
  • Mihai Cioc (11.25.2002@05:59:57PM EST)
  • Paul Reiners (11.26.2002@04:25:03PM EST)
  • Liu Wei (11.28.2002@02:55:00AM EST)
  • Taku Tamagawa (11.28.2002@03:38:46AM EST)
  • (11.28.2002@03:38:46AM EST)
  • Guler Amos (11.28.2002@01:10:42PM EST)
  • Nikhil Sahasrabudhe (11.29.2002@02:43:11AM EST)
  • Biju Mohan (11.29.2002@04:15:36AM EST)
  • Paul Gover (11.29.2002@05:25:15AM EST)
  • Ebi Aharpour (11.30.2002@11:19:51AM EST)
  • Vaithianathan A (12.02.2002@04:23:28AM EST)

Related posts