Ponder This Challenge - September 2016 - Seating four people for 24 hours

Ponder This Challenge:

It is impossible to seat three people (Alice, Bob, and Charlie) in three places for six hours, while changing places each hour in such a way that each hour has a different seating permutation and no one stays in his or her chair during two consecutive hours. Here is an "almost" solution:

A B C A B C
B C A C A B
C A B B C A

The only violation is the "B B" in the middle of the third line.

Our challenge for this month is to design a seating plan for four people for 24 hours in such a way that they don't repeat the same seating arrangement, and the number of violations is minimal, where violations refer to the same person sitting in the same place he sat in during one of the two preceding hours.

Solution

• Click here to view the solution

  Motty Porat got a '*' as the only solution which proved optimality:

  Dear Ponder,
  Phew... This was something else!
  But I'm thankful that 17 years after I learned that finite groups had interesting structures, something has finally forced me to delve into one.
  Here is my solution, with only one violation, and a proof that there must be a violation.

  CBACBADBCDABDCADBCDABDCA
  BACDABCDABDCADBCDABDCABC
  DCBADCBADCBACBDACBACDBAD
  ADDBCDACBACDBACBADCBACDB

  The process:

      Let p[1]..p[24] be the ordering of the permutations. Since the permutations are a group, we can talk about their quotients r[1]..r[23] such that:
          p[t+1] = p[t] * r[t]
          p[t+2] = p[t] * r[t] * r[t+1]
      In order to avoid violations, r[t], r[t+1], and r[t]*r[t+1] must be shuffles - permutations that move all elements.
      There are nine shuffles, which are generated by three of them:
          a = 3142     a^2 = 4321     a^3 = 2413
          b = 4123     b^2 = 3412     b^3 = 2341
          c = 4312     c^2 = 2143     c^3 = 3421
  

  Notice that the order of a, b, and c is 4.
  Looking at the multiplication table of the shuffles, we can see that:

  1. They generate the entire group of permutations.- The products of two squares is the third one, e.g. a^2 * b^2 = c^2.  (from the a,b,c above)- Any other product of shuffles is not a shuffle, e.g. a*b = 2314; the 4 is at the 4th place.

      As said, r[t], r[t+1], and r[t]*r[t+1] must be shuffles. Therefore r[t] and r[t+1] must be either:
          (I)   powers of the same generator, e.g.  a^3 and a^2  =>  r[t]*r[t+1] = a^5 = a.
          (II)  squares, e.g.  b^2 and a^2  =>  r[t]*r[t+1] = c^2.
              - "The fundamental law of Ponder 9/16"
      
      The series   a^2, a, a^2, b^2, b, b^2, a^2, a, a^2, ...   satisfies these requirements alternatively.
      My solution is this series plus some improvisations at the ends. They include a violation (r[2] is not a shuffle), but luckily, both r[1]*r[2] and r[2]*r[3] are again shuffles, so the violation does not propagate to neighbors of neighbors!
  

  The breakthrough:

  Since the squares (a^2, b^2, c^2) play an important role, let's check their effect on the other elements.
  Let P = all 24 permutations;
  Id = the unit element = 1234;
  G = {Id, a^2, b^2, c^2} = {Id, a^2, b^2, a^2*b^2} = the subgroup of the squares.
  The quotient group P/G comprises 6 cosets of 4 elements. I spared you their exact values.. For each x, multiplying x by the members of G (a^2, b^2, c^2) keeps it in the same coset, of course (xG), whereas multiplying x by a, b, or c  jumps to a different coset in an orderly fashion:

  My solution:

  A proof that there must be a violation:

  Back to the "fundamental law", let's divide the series of quotients (r[1]..r[23]) to sub-sequences with the same generator, e.g.  [ a^2, a, a^2 ].
  Each sub-sequence is at most 3 items long*, so there are at least 8 sub-sequences, and thus 7 joint-points. The joints are two squares, e.g.  r[t] = a^2,  r[t+1] = b^2.  But then, p[t], p[t+1], and p[t+2] are all in the same coset. There are 6 cosets, so we can't visit them 7 times (and "burn" 3 elements each time) without duplication!

  * If, for example, r[1], r[2], r[3], and r[4] were powers of a, then p[1], p[2], p[3], p[4], and p[5] would be p[1] times a power of a (including a^0). But there are only four different powers of a, and therefore one will repeat.

Solvers

• Emir Haleva (28/08/2016 06:29 PM IDT)
• Bert Dobbelaere (28/08/2016 07:15 PM IDT)
• David Greer (29/08/2016 02:21 AM IDT)
• Oleg Vlasii (29/08/2016 02:41 AM IDT)
• Serge Batalov (29/08/2016 09:30 AM IDT)
• Kang Jin Cho (29/08/2016 10:49 AM IDT)
• Alex Fleischer (29/08/2016 12:16 PM IDT)
• Robert Gerbicz (29/08/2016 01:33 PM IDT)
• Lorenz Reichel (29/08/2016 03:19 PM IDT)
• Shirish Chinchalkar (29/08/2016 04:36 PM IDT)
• Francis Golding (29/08/2016 05:28 PM IDT)
• Todd Will (29/08/2016 10:19 PM IDT)
• Siddharth Joshi (29/08/2016 10:30 PM IDT)
• Joaquim Neves Carrapa (30/08/2016 01:04 AM IDT)
• Jesse Rearick (30/08/2016 02:41 AM IDT)
• David F.H. Dunkley (30/08/2016 03:41 AM IDT)
• Yan-Wu He (30/08/2016 04:38 AM IDT)
• Bryce Fore (30/08/2016 06:59 AM IDT)
• Nyles Heise (30/08/2016 07:53 AM IDT)
• Sergey Koposov (30/08/2016 01:22 PM IDT)
• Paolo Farinelli (30/08/2016 06:00 PM IDT)
• Tom Sirgedas (30/08/2016 09:08 PM IDT)
• Harald Bögeholz (30/08/2016 09:32 PM IDT)
• Rob Pratt (30/08/2016 11:43 PM IDT)
• Andreas Stiller (30/08/2016 07:59 PM IDT)
• Daniel Chong Jyh Tar (31/08/2016 04:45 PM IDT)
• Balakrishnan Varadarajan (31/08/2016 06:32 PM IDT)
• Jamie Jorgensen (31/08/2016 07:55 PM IDT)
• Thomas Egense (01/09/2016 03:14 PM IDT)
• Aviv Nisgav (01/09/2016 04:09 PM IDT)
• Ran Sharon (01/09/2016 10:00 PM IDT)
• Hugo Pfoertner (01/09/2016 11:46 PM IDT)
• Ofer Springer (02/09/2016 01:18 AM IDT)
• James Dow Allen (02/09/2016 02:38 PM IDT)
• Joseph DeVincentis (02/09/2016 06:26 PM IDT)
• Florian Fischer (03/09/2016 02:26 AM IDT)
• Peter Gerritson (03/09/2016 04:43 AM IDT)
• Reiner Martin (03/09/2016 09:36 AM IDT)
• LaurV (03/09/2016 10:35 AM IDT)
• Nis Jørgensen (03/09/2016 03:35 PM IDT)
• Nigel Brumpton (03/09/2016 04:26 PM IDT)
• Arthur Vause (03/09/2016 05:59 PM IDT)
• Goh Koon Hui Geoffrey (04/09/2016 02:11 AM IDT)
• Julian Ma (04/09/2016 07:54 AM IDT)
• Marcelo De Barros (04/09/2016 05:32 PM IDT)
• Dan Ismailescu (04/09/2016 06:42 PM IDT)
• Gary M. Gerken (04/09/2016 08:27 PM IDT)
• George W Barnett (04/09/2016 10:53 PM IDT)
• Dejan Stakic (05/09/2016 09:44 AM IDT)
• Evert van Dijken (05/09/2016 09:45 AM IDT)
• Teake Nutma (05/09/2016 10:13 AM IDT)
• Liubing Yu (06/09/2016 09:27 AM IDT)
• Larry Kearney (06/09/2016 05:28 PM IDT)
• Eric Koh (06/09/2016 11:32 PM IDT)
• Leandro Augusto de Araújo Silva (07/09/2016 10:17 AM IDT)
• Dezhi Zhao (07/09/2016 10:27 PM IDT)
• Claudio Baiocchi (07/09/2016 11:22 PM IDT)
• Armin Krauss (08/09/2016 10:30 AM IDT)
• Stijn Vermeeren (08/09/2016 04:28 PM IDT)
• Pål Hermunn Johansen (08/09/2016 05:38 PM IDT)
• Thomas Satzger (09/09/2016 08:12 PM IDT)
• Jimmy Waters (13/09/2016 12:54 AM IDT)
• Warren Yazzie (13/09/2016 08:40 AM IDT)
• Gale Greenlee (13/09/2016 06:23 PM IDT)
• Yevgeniy Parfilko & Andrew Tzorfas (14/09/2016 09:43 PM IDT)
• Itay Hazan (15/09/2016 01:46 AM IDT)
• Luiz Friedrich (15/09/2016 10:54 AM IDT)
• Robert Lang (16/09/2016 12:24 PM IDT)
• Benjamin Lui (16/09/2016 03:54 PM IDT)
• Tyler Mullen (17/09/2016 07:01 AM IDT)
• John Spurgeon (19/09/2016 03:46 PM IDT)
• Mathias Schenker (19/09/2016 10:54 PM IDT)
• Tyler Moyes (20/09/2016 06:16 AM IDT)
• Jordan Leaman (20/09/2016 06:23 AM IDT)
• *Motty Porat (20/09/2016 03:23 PM IDT)
• Qibin Zhou (21/09/2016 04:43 PM IDT)
• Shouly Dan & Tamir Ganor (21/09/2016 06:42 PM IDT)
• Yian Ann Xu (22/09/2016 02:18 PM IDT)
• Clive Tong (22/09/2016 06:08 PM IDT)
• Mouad Faik (22/09/2016 10:34 PM IDT)
• Fabio Michele Negroni (23/09/2016 04:00 PM IDT)
• Hyunsun (Heidi) Kim (24/09/2016 08:59 PM IDT)
• Thomas Lee (24/09/2016 09:33 PM IDT)
• Jang Hun Choi (24/09/2016 10:47 PM IDT)
• Jose Coelho Soares (25/09/2016 02:54 PM IDT)
• Ji Eun Kim (25/09/2016 05:22 PM IDT)
• Yuwon Elaine Moon (25/09/2016 06:24 PM IDT)
• Joehyun Kim (26/09/2016 02:25 AM IDT)
• Wilder Boyden (26/09/2016 09:12 AM IDT)
• Sri Mallikarjun J (26/09/2016 04:17 PM IDT)
• Dennis Evans (26/09/2016 09:11 PM IDT)
• Joo Sung Yi (26/09/2016 11:10 PM IDT)
• Muralidhar Seshadri (27/09/2016 12:29 AM IDT)
• Jackie Byeongyeon Ryu (27/09/2016 02:29 AM IDT)
• Govind A N (27/09/2016 06:23 AM IDT)
• Raymond Lo (27/09/2016 11:50 AM IDT)
• Emilio Del Tessandoro (27/09/2016 01:26 PM IDT)
• Fabio Filatrella (27/09/2016 04:06 PM IDT)
• Scott Walters (27/09/2016 04:52 PM IDT)
• Mark Stuckel (28/09/2016 08:14 AM IDT)
• Edward Bentley (29/09/2016 11:13 AM IDT)
• Alessandro Marzo (29/09/2016 06:32 PM IDT)
• Philip Kinlen (30/09/2016 07:15 PM IDT)
• Kareem Oliver-Diaz (01/10/2016 04:59 AM IDT)
• Radu-Alexandru Todor (01/10/2016 06:26 PM IDT)
• Martin Sergio H. Faester (02/10/2016 01:49 AM IDT)
• Slavisa Pajkanovic (02/10/2016 07:50 PM IDT)