August 2022 - Challenge
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:
AABDACCCCCCDABBA
The following arrangement is illegal because B,C start together after A,D finish; A dances on the left side and suddenly switches to the middle; and B,D switch sides.
AABBBADBBDCCAABD
There are 16 ways to perform a n=1 dance, 120 ways to perform an n=2 dance, and 17,342,172 ways to perform an n=8 dance. Since numbers grow rapidly, we compute them modulo N=3141592653. For n=128, the number of ways modulo N is 2,484,449,895.
Your goal: Compute the number of ways for n=2^{24}=16,777,216 modulo N=3141592653
A Bonus "*" will be given for computing the number of ways for n=2^{256} modulo N=3141592653
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
Challenge:
31/07/2022 @ 11:30:00 AM EST
Solution:
04/09/2022 @ 12:00 PM EST
List Updated:
31/08/2022 @ 21:30 PM EST
People who answered correctly:
*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)