Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

August 2022 - Challenge

<< July

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:


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.


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: 08/08/2022 @ 13: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)
*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)