Puzzle
4 minute read

Ponder This Challenge - March 2018 - Alice and Bob and Six Switches

Alice and Bob are given an interesting challenge. Alice will be given a random vowel (A, E, I, O, or U) in a room without Bob with six randomly set toggle (on/off) switches. She may change the state of at most one switch and then leave the room without talking to Bob. Bob must then enter the room and discover the secret vowel Alice was given.

Before Alice enters the room, she and Bob agree on a plan. Their strategy is to declare the unknown (as yet) vowel as a function of the new state of the switches.

What exactly is their suggestion?

Supply your answer as a 64-long string of vowels: the first representing when all six switches are off; the second representing when the first five are off and the last is on; ... until the last vowel representing when all six switches are on.

For example, a similar challenge with just three switches and three letters A, B, and C can be solved (why?) by AABCCBAC, which stands for:

A	A	B	C	C	B	A	C

0	0	0	0	1	1	1	1

0	0	1	1	0	0	1	1

0	1	0	1	0	1	0	1

Solution

  • Build a graph with 64 vertices (one for every state of the six switches) and edges between any two states that are only one toggle apart. The challenge is to color this graph in five colors (one for each vowel) such that every color appears in each subset of seven vertices, each of which contains a vertex and all its six neighbors. This problem can be solved, for example, using Mixed Integer Programming (MIP) technique, like the CPLEX program written by Alex Fleischer (thanks!).

    Andreas Stiller told us that the smallest solution (lexicographically) is AAAAEEEIIIOOUUOUOUIEIAUOEAUAAOIEUOUUOOIIIEEEAAAAEIOAAUAEOUAIEIUO

Solvers

  • Oleg Vlasii (28/02/18 01:41 PM IDT)
  • Bert Dobbelaere (28/02/18 07:52 PM IDT)
  • Alex Fleischer (28/02/18 09:00 PM IDT)
  • Andreas Stiller (01/03/18 01:07 AM IDT)
  • Alper Halbutogullari (01/03/18 06:01 AM IDT)
  • Kang Jin Cho (01/03/18 05:36 PM IDT)
  • Muralidhar Seshadri (02/03/18 08:56 AM IDT)
  • Clive Tong (02/03/18 10:42 AM IDT)
  • James Dow Allen (02/03/18 08:02 PM IDT)
  • Reiner Martin (02/03/18 11:08 PM IDT)
  • Rob Pratt (02/03/18 11:16 PM IDT)
  • Balakrishnan Varadarajan (03/03/18 12:12 AM IDT)
  • Todd Will (03/03/18 02:29 AM IDT)
  • Leonid Kalmankin (03/03/18 02:29 AM IDT)
  • Oleg Selin (03/03/18 02:40 AM IDT)
  • Yan-Wu He (03/03/18 06:44 PM IDT)
  • Pavel Glasnov (03/03/18 08:51 PM IDT)
  • Francis Golding (03/03/18 11:14 PM IDT)
  • Joaquim Neves Carrapa (03/03/18 11:48 PM IDT)
  • Andrei Tsygankov (04/03/18 05:42 PM IDT)
  • Shuky Dan & Tamir Ganor (04/03/18 09:58 PM IDT)
  • Walter Sebastian Gisler (05/03/18 09:53 AM IDT)
  • Mathias Schenker (05/03/18 10:49 PM IDT)
  • David Greer (06/03/18 01:08 AM IDT)
  • Erik Hostens (06/03/18 12:11 PM IDT)
  • Mykola Zubach (06/03/18 07:52 PM IDT)
  • Pranjal Agrawal (06/03/18 08:44 PM IDT)
  • Andreas Knüpfer (06/03/18 10:51 PM IDT)
  • Kevin Bauer (07/03/18 12:41 AM IDT)
  • Hanlin Ren (07/03/18 10:45 AM IDT)
  • Hugo Pfoertner (07/03/18 02:54 PM IDT)
  • Andreas Eisele (07/03/18 03:03 PM IDT)
  • Shirish Chinchalkar (08/03/18 03:59 AM IDT)
  • Robert Lang (09/03/18 11:11 AM IDT)
  • Guillaume Escamocher (09/03/18 06:37 PM IDT)
  • Graham Hemsley (09/03/18 07:29 PM IDT)
  • Bart De Vylder (09/03/18 09:59 PM IDT)
  • Pål Hermunn Johansen (10/03/18 12:13 AM IDT)
  • Anatoliy Vesnin (10/03/18 02:15 PM IDT)
  • Maxime Raynal (10/03/18 05:29 PM IDT)
  • Harald Bögeholz (11/03/18 12:45 AM IDT)
  • Hugues Juille (11/03/18 02:42 PM IDT)
  • Tom Sirgedas (12/03/18 16:02 PM IDT)
  • Gunilla Bergendahl (12/03/18 11:09 PM IDT)
  • Kaifei Chen (14/03/18 04:39 AM IDT)
  • Azamat Berdyshev (14/03/18 10:29 AM IDT)
  • Uoti Urpala (14/03/18 10:40 PM IDT)
  • Nguyen Khac Tung (15/03/18 10:59 AM IDT)
  • Balzac Angela (15/03/18 04:52 PM IDT)
  • Vladimir Volevich (15/03/18 05:32 PM IDT)
  • Dmitry Serbin (15/03/18 05:54 PM IDT)
  • Vicom Nguyen (15/03/18 07:46 PM IDT)
  • Michael Rosola (15/03/18 09:05 PM IDT)
  • Chun Kai Ling (16/03/18 05:36 AM IDT)
  • Yuval Nezri (16/03/18 09:51 AM IDT)
  • Xiu-Han Wang (16/03/18 06:20 PM IDT)
  • Michael Liepelt (16/03/18 06:30 PM IDT)
  • Eden Saig (16/03/18 06:43 PM IDT)
  • Rickard Björklund (17/03/18 01:01 AM IDT)
  • Vladimir M. Milovanović (18/03/18 03:55 PM IDT)
  • Paolo Farinelli (20/03/18 01:54 AM IDT)
  • Davin Choo (22/03/18 02:07 PM IDT)
  • Peter Gerritson (22/03/18 21:05 PM IDT)
  • Sri Mallikarjun J (23/03/18 10:53 AM IDT)
  • Guangzhong Sun (23/03/18 02:26 PM IDT)
  • Roland Postle (24/03/18 12:10 AM IDT)
  • Gumpina Rama Krishna Chaitanya (24/03/18 09:29 PM IDT)
  • Tyler Mullen (25/03/18 09:21 AM IDT)
  • Lakshman Inkulu (25/03/18 02:34 PM IDT)
  • JJ Rabeyrin (26/03/18 01:54 AM IDT)
  • Daniel Chong Jyh Tar (27/03/18 05:39 AM IDT)
  • Sai Kishore Datti (27/03/18 12:32 PM IDT)
  • Sasi Teja Alluri (27/03/18 04:37 PM IDT)
  • Nyles Heise (27/03/18 05:09 PM IDT)
  • Bharatkumar Aryasomayajula (28/03/18 05:48 PM IDT)
  • Joehyun Kim (29/03/18 04:10 AM IDT)
  • Oscar Volpatti (29/03/18 05:28 AM IDT)
  • Lorenz Reichel (30/03/18 06:49 PM IDT)
  • Joonsoo Lee (31/03/18 08:33 PM IDT)
  • Tiffany Lee (31/03/18 10:38 PM IDT)
  • Li Li (01/04/18 02:57 AM IDT)
  • John Park (01/04/18 03:58 AM IDT)
  • Celine Lee (01/04/18 04:01 PM IDT)
  • David F. H. Dunkley (02/04/18 12:44 AM IDT)
  • Radu-Alexandru Todor (02/04/18 05:00 AM IDT)

Related posts