Ponder This Challenge - January 2005 - 7-colored 35 beads necklace

Ponder This Challenge:

Puzzle for January 2005

Our New Years puzzle was submitted by John G. Fletcher,
who heard it from Marc Roth.

A necklace is made up of 35 beads forming a closed loop, each bead being of one of 7 distinct colors. Find an arrangement for the beads such that every one of the 35 combinations of the 7 colors taken 3 at a time (i.e. each triple of different colors) occurs exactly once as a set of 3 consecutive beads.

The first 100 people who answer correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

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

• Click here to view the solution

  Answer:

  There is no obvious general way to attack this problem. However, with the seven colors called A, B, 0, 1, 2, 3, 4, one solution is:

  1243A0B 2304A1B 3410A2B 4021A3B 0132A4B.

  The spaces partition the necklace into five 7-bead segments to call attention to the symmetry: Any bead and the bead 7 positions further along are of the same color when that color is A or B; otherwise the latter is 1 more (modulo 5) than the former. QED

  This solution does not readily extend to other numbers of colors. It is not unique:

  1. There are 14 solutions with the above symmetry. One segment of each of these solutions is:

  1243A0B, 0231A0B, 3014A0B, 0312A0B, 1023A0B, 2314A0B, 2341A0B, 0214A0B, 0341A0B, 3124A0B, 1024A0B, 3012A0B, 0243A0B, 0324A0B.

  2. The colors of a solution may be arbitrarily permuted, yielding a solution with perhaps a modestly different symmetry. Among these permutations are those having the same effect as reversing the necklace and/or changing the increment for the segment-to-segment color changes.

  3. Given a solution, any sequence of beads such that the last two beads in the sequence are the same as the first two but in the reverse order, may be reversed to yield a new solution, which generally has no simple symmetry. For example, in the original solution the sequence 43A0B 2304A1B 34 may be reversed, yielding the solution:

  1243B1A 4032B0A 3410A2B 4021A3B 0132A4B.

  (James B. Shearer pointed out this technique.)

  4. Patrick LoPresti investigated solutions for other choces of the parameters:

  "So far, my program has found these solutions for (n,m,nCm), where n is the number of colors, m is the size of the subset, and nCm is n-choose-m. I have omitted the trivial cases of m=1 and m=n-1, as well as the unsolvable cases where n does not divide nCm.

  (5,2,10)
  0 1 2 0 3 1 4 2 3 4

  (5,3,10)
  no solution

  (7,2,21)
  0 1 2 0 3 1 4 0 5 1 6 2 3 4 2 5 3 6 4 5 6

  (7,3,35)
  0 1 2 3 0 1 4 2 0 5 1 2 6 0 3 4 1 5 6 2 4 3 5 0 4 6 3 2 5 4 6 1 3 5 6

  (7,4,35)
  0 1 2 3 4 0 1 2 5 3 0 1 6 4 2 0 5 6 3 1 4 5 2 6 3 0 4 5 1 6 2 3 4 5 6

  (7,5,21)
  No solution.

  (8,3,56)
  still running...

  (8,5,56)
  0 1 2 3 4 5 0 1 2 3 6 4 0 1 2 7 5 3 0 1 6 7 4 2 0 5 6 3 4 7 1 2 5 6 0 7 3 4 1 5 6 2 3 7 0 4 5 1 6 7 3 2 4 5 6 7"

  Thanks, Patrick

  5. John Fletcher remarks:

  An (n,2) necklace always exists when n is odd, as the following recursive construction shows: Label the n colors with the integers from 0 to n-1. Given a sequence of n(n-1)/2 beads (starting with 0) for a necklace of n colors, a sequence for n+2 colors is obtained by appending to that sequence the following sequence of 2n+1 beads: 0, n, 1, n+1, 2, n, 3, n+1, ... , n+1, n-3, n, n-2, n+1, n-1, n, n+1 . (Except for the final n+1, alternate beads form two subsequences, each of n beads: 0, 1, 2, ..., n-1 and n, n+1, n, n+1, ..., n.) The recursion begins at n = 1 with an empty necklace. This is followed by:
  for n = 3: 0, 1, 2;
  for n = 5: 0, 1, 2, 0, 3, 1, 4, 2, 3, 4;
  for n = 7: 0, 1, 2, 0, 3, 1, 4, 2, 3, 4, 0, 5, 1, 6, 2, 5, 3, 6, 4, 5, 6;
  etc.

  It is not difficult to see that each sequence retains all adjacent color pairings from its predecessor, to which it adds the pairing of the two new colors with each other and all 2n pairings of each of them with each of the n old colors.

  ---

  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

• Patrick J. LoPresti (01.04.2005 @09:53:17 AM EDT)
• Hagen von Eitzen (01.04.2005 @11:26:04 AM EDT)
• Amin Ahmad (01.04.2005 @12:17:53 PM EDT)
• Sonny Kunnakkat (01.04.2005 @12:48:56 PM EDT)
• Daniel Bitin (01.04.2005 @01:00:46 PM EDT)
• David Friedman (01.04.2005 @01:38:16 PM EDT)
• Eugene Vasilchenko (01.04.2005 @02:37:42 PM EDT)
• Brad Austin (01.04.2005 @04:21:54 PM EDT)
• Alan O'Donnell (01.04.2005 @04:40:38 PM EDT)
• Andreas Kabel (01.04.2005 @05:01:23 PM EDT)
• Allan Lazarovici (01.04.2005 @06:06:30 PM EDT)
• Jeff Shute (01.04.2005 @06:42:13 PM EDT)
• Johannes Schindelin (01.04.2005 @07:36:14 PM EDT)
• Emile Joubert (01.04.2005 @08:10:42 PM EDT)
• Praveen Kumar J (01.04.2005 @08:54:49 PM EDT)
• Seung Jun (01.04.2005 @09:06:27 PM EDT)
• Leonardo Liang (01.05.2005 @01:40:22 AM EDT)
• Daniel Chong Jyh Tar (01.05.2005 @01:58:07 AM EDT)
• Dion K Harmon (01.05.2005 @03:07:03 AM EDT)
• Victor Chang (01.05.2005 @05:08:49 AM EDT)
• IQSTAR (01.05.2005 @05:20:06 AM EDT)
• Jose H. Nieto (01.05.2005 @05:37:32 AM EDT)
• Raicho Tchalkov (01.05.2005 @07:03:31 AM EDT)
• Yong Liu (01.05.2005 @09:21:06 AM EDT)
• Faron Moller (01.05.2005 @11:00:55 AM EDT)
• Antonio Manuel Gutiérrez Fernández (01.05.2005 @12:27:45 PM EDT)
• Ken Duisenberg (01.05.2005 @02:05:54 PM EDT)
• Pascal Brisset (01.05.2005 @02:38:28 PM EDT)
• Alexander Navernyuk (01.05.2005 @03:05:25 PM EDT)
• Ken Crounse (01.05.2005 @05:37:15 PM EDT)
• Dennis Langdeau (01.05.2005 @07:15:15 PM EDT)
• Jaume Simon Gispert (01.05.2005 @07:47:05 PM EDT)
• Oskar Sigvardsson (01.06.2005 @12:19:43 AM EDT)
• Max Alekseyev (01.06.2005 @01:30:50 AM EDT)
• Aditya K. Prasad (01.06.2005 @02:50:49 AM EDT)
• John Hart (01.06.2005 @03:06:29 AM EDT)
• Dharmadeep Muppalla (01.06.2005 @03:56:12 AM EDT)
• Mikhail Barrett (01.06.2005 @04:55:36 AM EDT)
• Gary M Gerken (01.06.2005 @05:04:11 AM EDT)
• Francis Golding (01.06.2005 @07:22:46 AM EDT)
• Bert Fischer (01.06.2005 @08:09:22 AM EDT)
• Peter Petrov (01.06.2005 @09:09:44 AM EDT)
• John Tromp (01.06.2005 @10:35:23 AM EDT)
• Ari (01.06.2005 @11:39:00 AM EDT)
• Rob Pratt (01.06.2005 @01:05:45 PM EDT)
• Mike Rousse (01.06.2005 @02:03:34 PM EDT)
• Sean Henderson (01.06.2005 @07:06:03 PM EDT)
• Rustam Miftakhutdinov (01.06.2005 @11:31:56 PM EDT)
• James Dow Allen (01.07.2005 @04:09:28 AM EDT)
• Mocanu Cristian (01.07.2005 @09:26:01 AM EDT)
• Roger Duthie (01.07.2005 @02:34:05 PM EDT)
• Alexandru Sofronia (01.07.2005 @03:07:34 PM EDT)
• Leonid A Broukhis (01.07.2005 @05:51:57 PM EDT)
• Scott Hotes (01.08.2005 @02:30:43 AM EDT)
• Jinhong Kim (01.08.2005 @11:15:54 AM EDT)
• Andrew Scherbakov (01.08.2005 @12:15:21 PM EDT)
• Jack Rouse (01.08.2005 @07:21:31 PM EDT)
• Alex Tikhonov (01.08.2005 @11:25:54 PM EDT)
• Rico Blaser (01.09.2005 @02:59:33 AM EDT)
• Dinesh Layek (01.09.2005 @05:27:34 AM EDT)
• Bhaskara Aditya (01.09.2005 @06:22:51 AM EDT)
• Ajay Reddy Mallepally (01.09.2005 @08:52:04 AM EDT)
• Mallepally (01.09.2005 @08:52:04 AM EDT)
• Dmitry Litvinenko (01.09.2005 @09:02:11 AM EDT)
• Fred Youhanaie (01.09.2005 @05:30:44 PM EDT)
• Wolfgang Kais (01.10.2005 @01:18:04 AM EDT)
• Luke Pebody (01.10.2005 @07:23:44 AM EDT)
• Brian Schroeder (01.10.2005 @09:13:41 AM EDT)
• Visegrady Tamas (01.11.2005 @07:06:47 PM EDT)
• Kim Se Kwon (01.11.2005 @10:50:56 PM EDT)
• Aditya Kamat (01.12.2005 @01:44:06 AM EDT)
• Robert Trimble (01.12.2005 @03:57:30 AM EDT)
• Clive Tong (01.12.2005 @04:31:47 AM EDT)
• Harish J P (01.12.2005 @07:35:17 AM EDT)
• Joe BGI SF (01.12.2005 @12:07:16 PM EDT)
• Fendel (01.12.2005 @12:07:16 PM EDT)
• Sergey Povetkin (01.12.2005 @12:28:06 PM EDT)
• Divyesh Dixit (01.12.2005 @01:00:00 PM EDT)
• Daniel Carrapa (01.12.2005 @06:05:29 PM EDT)
• Sumanth Jagannath (01.13.2005 @12:24:36 AM EDT)
• Vineet Dwivedi (01.13.2005 @01:30:14 AM EDT)
• Arup Salui (01.13.2005 @07:52:27 AM EDT)
• Pratik P Dixit (01.13.2005 @12:52:16 PM EDT)
• Dan Dima (01.13.2005 @12:55:00 PM EDT)
• Ernst Munter (01.13.2005 @01:18:26 PM EDT)
• Praveen Jain (01.14.2005 @03:31:14 AM EDT)
• Kalyana Chakravarthy (01.14.2005 @11:29:18 AM EDT)
• Adel El-Atawy (01.15.2005 @03:56:23 AM EDT)
• Philippe Fondanaiche (01.15.2005 @10:14:49 AM EDT)
• Paul Sonier (01.15.2005 @07:49:03 PM EDT)
• Steffen Wolf (01.15.2005 @08:29:31 PM EDT)
• Igor Malashkin (01.17.2005 @02:54:22 AM EDT)
• Alexey Vorobyov (01.17.2005 @09:14:42 PM EDT)
• Kapil K Jain (01.18.2005 @12:57:34 AM EDT)
• BlueFrog (01.18.2005 @09:09:24 AM EDT)
• Tom Rokicki (01.18.2005 @02:10:27 PM EDT)
• Lucas Sidiropoulos (01.18.2005 @03:02:11 PM EDT)
• Siva Dirisala (01.18.2005 @03:22:32 PM EDT)
• Mihai Cioc (01.20.2005 @12:19:45 PM EDT)
• Bart De Vylder (01.20.2005 @06:30:53 PM EDT)
• Robert Danek (01.21.2005 @07:51:49 PM EDT)
• Catalin Buzoiu (01.22.2005 @09:04:11 AM EDT)
• Naftali Spiegel (01.23.2005 @02:23:44 AM EDT)