Ponder This Challenge - August 2022 - Safety dance

Safety dance

A dance show consists of four dancers, designated A, B, C, and D, who dance on a stage for $n$ units of time. However, due to safety concerns, they cannot all dance together; either a single dancer performs in the middle section, or two dancers dance on the right and left parts of the stage, respectively.

When on the sides of the stage, each dancer can dance for 1, 2, or 3 units of time before being replaced by a dancer currently not on the stage. A dancer in the middle section must be replaced in 1 unit of time, either by another dancer in the middle or two others in the side sections. Dancers cannot switch places on stage directly from one unit of time to the next.

As a last rule, if two dancers need to be replaced at the same time, they must be replaced by a single dancer in the middle.

Here’s an example of a dance arrangement that takes 8 units of time in total. The top row represents the dancer on the right side of the stage and the bottom row the dancer on the left side of the stage in any given column representing a unit of time, unless those values are identical, which indicates a dancer in the middle of the stage:

AABDACCC
CCCDABBA

Solution

• Click here to view the solution

  August 2022 Solution:

  The numerical solutions are

  2524614399 for 2^24
  920321499 for 2^256

  The sequence s(n) for the number of ways to perform an n-time dance satisfies a recurrence relation, which can be systematically obtained by constructing a state transition diagram and computing the recurrence relation from its reprenting matrix using standard combinatorial techniques. To compute the recurrence relation for large numbers in general can be done using Fiduccia's algorithm see but here since n is a power of 2, it can be done using iterative squaring.

Solvers

• *Lorenz Reichel (2/8/2022 12:51 PM IDT)
• *Lazar Ilic (2/8/2022 2:06 PM IDT)
• *Bertram Felgenhauer (2/8/2022 4:31 PM IDT)
• *John Tromp (2/8/2022 4:45 PM IDT)
• *Paul Revenant (2/8/2022 5:04 PM IDT)
• *Bert Dobbelaere (2/8/2022 9:17 PM IDT)
• *Uoti Urpala (2/8/2022 11:17 PM IDT)
• *Sean Egan (3/8/2022 1:02 AM IDT)
• *Laurent Lessard (3/8/2022 1:23 AM IDT)
• *Phil Proudman (3/8/2022 6:44 AM IDT)
• Graham Hemsley (3/8/2022 6:13 PM IDT)
• *Amos Guler (3/8/2022 10:53 PM IDT)
• *Reiner Martin (4/8/2022 12:39 AM IDT)
• *Grant Boudreaux (4/8/2022 1:02 AM IDT)
• Turgay Yuktas (4/8/2022 1:07 AM IDT)
• *Vladimir Volevich (4/8/2022 10:36 AM IDT)
• *Alper Halbutogullari (4/8/2022 12:36 PM IDT)
• *Victor Chang (4/8/2022 3:00 PM IDT)
• *Daniel Bitin (4/8/2022 6:10 PM IDT)
• *Liang HE (5/8/2022 2:51 AM IDT)
• *HC Zhu (5/8/2022 9:54 AM IDT)
• *Harald Bögeholz (5/8/2022 2:40 PM IDT)
• *Keith Schneider (5/8/2022 9:56 PM IDT)
• John Goh (5/8/2022 9:58 PM IDT)
• *Peter Moser (5/8/2022 10:01 PM IDT)
• *Jonathan Evans (6/8/2022 7:42 AM IDT)
• *James Miles (6/8/2022 8:34 AM IDT)
• *Willem Hendriks (6/8/2022 12:40 PM IDT)
• *Gary M. Gerken (6/8/2022 4:42 PM IDT)
• *Eran Vered (6/8/2022 9:53 PM IDT)
• Shirish Chinchalkar (7/8/2022 3:23 PM IDT)
• *Nyles Heise (8/8/2022 7:41 AM IDT)
• *Balakrishnan V (8/8/2022 7:55 AM IDT)
• *Stéphane Higueret (8/8/2022 8:10 AM IDT)
• *Andreas Stiller (8/8/2022 1:23 PM IDT)
• *Dominik Reichl (8/8/2022 3:25 PM IDT)
• *Vardhan Walavalkar (8/8/2022 6:57 PM IDT)
• *Paul Shaw (8/8/2022 9:47 PM IDT)
• *Sanandan Swaminathan (9/8/2022 4:19 PM IDT)
• *Lorenzo Gianferrari Pini (9/8/2022 10:08 PM IDT)
• *Todd Will (10/8/2022 5:20 PM IDT)
• *Richard Liu (10/8/2022 11:42 PM IDT)
• Latchezar Christov (11/8/2022 12:48 PM IDT)
• Guillaume Escamocher (11/8/2022 6:23 PM IDT)
• Ralf Jonas (12/8/2022 12:01 PM IDT)
• *Joram Meron (12/8/2022 12:29 PM IDT)
• *David Greer (13/8/2022 7:58 PM IDT)
• Clive Tong (13/8/2022 9:55 PM IDT)
• *Dieter Beckerle (14/8/2022 7:56 AM IDT)
• **Dan Ismailescu (14/8/2022 7:59 AM IDT)
• *Daniel Chong Jyh Tar (14/8/2022 6:47 PM IDT)
• *Radu-Alexandru Todor (14/8/2022 11:16 PM IDT)
• *Karl Mahlburg (15/8/2022 2:42 AM IDT)
• *David F.H. Dunkley (17/8/2022 2:03 AM IDT)
• *James Lew (17/8/2022 5:30 PM IDT)
• *Ananda Raidu (18/8/2022 1:21 PM IDT)
• *Tim Walters (18/8/2022 1:40 PM IDT)
• Fabio Michele Negroni (22/8/2022 2:00 PM IDT)
• *Motty Porat (22/8/2022 10:03 PM IDT)
• *Dan Dima (23/8/2022 4:35 PM IDT)
• *Li Li (23/8/2022 5:07 PM IDT)
• *Kang Jin Cho (24/8/2022 6:54 PM IDT)
• Kipp Johnson (25/8/2022 5:57 AM IDT)
• *Chris Shannon (25/8/2022 8:33 AM IDT)
• Marco Bellocchi (25/8/2022 8:34 PM IDT)
• *Sachal Mahajan (25/8/2022 9:18 PM IDT)
• *Ali Gurel (27/8/2022 5:45 AM IDT)
• *George D. Logan (29/8/2022 5:50 AM IDT)
• *Andreas Puccio (30/8/2022 11:13 PM IDT)
• Kai Guttmann (31/8/2022 7:35 AM IDT)
• *Oscar Volpatti (31/8/2022 9:39 AM IDT)
• Alexander Strasser (31/8/2022 11:07 AM IDT)
• *Keun Hyong Kwak (31/8/2022 7:02 PM IDT)
• *Grace Yeeun Park (31/8/2022 7:05 PM IDT)
• *Teawoo Kim (31/8/2022 7:48 PM IDT)
• *Jessica Lee (31/8/2022 8:48 PM IDT)
• *Austin Lee (1/9/2022 2:24AM IDT)