Ponder This

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

April 2021 - Challenge

<< March May >>


A wheel of choice is marked with the numbers 1,2,...,n, and a prize is associated with each number.

A player faced with the wheel chooses some number q and starts spinning the wheel k times. On each spin, the wheel moves forward q steps in a clockwise direction and the number / prize reached is eliminated from the wheel (i.e., the player does not get it). After k such spins, all the prizes remaining on the wheel are gifted to the player.
At the beginning, the wheel's arrow points between 1 and n. If the wheel reaches the number t, t is removed from the wheel, the size of the remaining numbers are readjusted and evenly spaced, and the arrow is moved to the point in between t's left and right neighbors. Each step moves the wheel a little less than one number forward (so the wheel comes to rest on a number and not between two). So, if the wheel is right before 1 and performs 3 steps, it ends up on 3.

An example of the wheel for n=8:

And after three spins with q=5:

For a given n, we call a set of k numbers unwinnable if no matter what q the player chooses, he will not be able to win exactly this set after n-k spins. The game show wants to know the unwinnable sets of a given n to avoid handing out the best prizes.

For example, there are no unwinnable sets for n smaller than 9. For n=9, there are three unwinnable sets, all of size k=5:

(1, 2, 5, 8, 9)
(2, 3, 4, 5, 8)
(2, 5, 6, 7, 8)

Your goal: Find an n such that there is a set of unwinnable numbers for seven steps (i.e., the set is of size n-7). In your answer, supply the number n and the elements of the unwinnable set.



A bonus '*' for finding an unwinnable set which takes more than seven steps.




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/03/2021 @ 12:00 PM EST
Solution: 04/05/2021 @ 12:00 PM EST
List Updated: 03/05/2021 @ 12:00 PM EST

People who answered correctly:

*Lorenz Reichel (1/4/2021 10:57 PM IDT)
*Guillaume Escamocher (1/4/2021 11:27 PM IDT)
*Uoti Urpala (1/4/2021 11:55 PM IDT)
*Victor Chang (2/4/2021 3:19 AM IDT)
*K S (2/4/2021 4:46 AM IDT)
*Daniel Chong Jyh Tar (2/4/2021 7:48 AM IDT)
*Paul Revenant (2/4/2021 12:49 PM IDT)
*Eden Saig (2/4/2021 5:58 PM IDT)
Christofer Ohlsson (2/4/2021 6:35 PM IDT)
*Phil Proudman (2/4/2021 6:36 PM IDT)
*Sean Egan (2/4/2021 6:45 PM IDT)
Jordan Rinder (2/4/2021 7:34 PM IDT)
*Alper Halbutogullari (2/4/2021 10:03 PM IDT)
*Dominik Reichl (2/4/2021 11:37 PM IDT)
*James Dow Allen (2/4/2021 11:59 PM IDT)
Alex Fleischer (3/4/2021 12:27 AM IDT)
JJ Rabeyrin (3/4/2021 1:59 AM IDT)
*Andreas Stiller (3/4/2021 2:44 AM IDT)
*Walter Schmidt (3/4/2021 12:38 PM IDT)
*Reiner Martin (3/4/2021 7:34 PM IDT)
*Bert Dobbelaere (3/4/2021 9:06 PM IDT)
Steven Langerwerf (4/4/2021 4:04 AM IDT)
*Dieter Beckerle (4/4/2021 9:29 AM IDT)
*Florian Fischer (4/4/2021 1:01 PM IDT)
Graham Hemsley (4/4/2021 3:36 PM IDT)
Kamil Jarosz (4/4/2021 4:02 PM IDT)
*Clive Tong (4/4/2021 5:12 PM IDT)
David Smalling (4/4/2021 10:38 PM IDT)
*Hakan Summakoğlu (5/4/2021 2:01 AM IDT)
Ilya Tarygin (5/4/2021 2:53 PM IDT)
*Vladimir Volevich (5/4/2021 4:16 PM IDT)
*Nir Drucker (5/4/2021 4:55 PM IDT)
*Giorgos Kalogeropoulos (5/4/2021 7:01 PM IDT)
*Thomas Egense (5/4/2021 8:58 PM IDT)
*Cynthia Beauchemin (5/4/2021 9:10 PM IDT)
Govind Raj Jujare (5/4/2021 11:41 PM IDT)
*Marco Bellocchi (6/4/2021 1:24 AM IDT)
Michał Franczak (6/4/2021 2:57 AM IDT)
Colas Kerkhove (6/4/2021 12:04 PM IDT)
*Liubing Yu (6/4/2021 1:28 PM IDT)
Christoph Schmidt (6/4/2021 9:21 PM IDT)
Andrew Mullins (6/4/2021 10:01 PM IDT)
*Karl D’Souza (7/4/2021 2:03 AM IDT)
*Gil Citro (7/4/2021 5:24 AM IDT)
*Wang Longbu (7/4/2021 12:25 PM IDT)
*Markó Horváth (7/4/2021 6:20 PM IDT)
*Andreas Knüpfer (8/4/2021 3:59 PM IDT)
*Loukas Sidiropoulos (8/4/2021 4:57 PM IDT)
*Reda Kebbaj (8/4/2021 5:38 PM IDT)
Gary M. Gerken (8/4/2021 8:34 PM IDT)
*Tim Walters (9/4/2021 6:45 AM IDT)
*Latchezar Christov (9/4/2021 11:59 PM IDT)
Michael Liepelt (10/4/2021 2:09 PM IDT)
*Simeon Krastnikov (10/4/2021 4:30 PM IDT)
*Fabio Filatrella (10/4/2021 8:30 PM IDT)
Chris Shannon (11/4/2021 3:16 AM IDT)
*Thomas Pircher (11/4/2021 9:09 AM IDT)
*Daniel Bitin (11/4/2021 7:59 PM IDT)
*Nicolas Lopez (11/4/2021 10:08 PM IDT)
*Raymond Lo (12/4/2021 1:52 AM IDT)
*Bertram Felgenhauer (12/4/2021 3:17 AM IDT)
Colomban Basset (12/4/2021 9:39 AM IDT)
Willem H Hendriks (12/4/2021 6:37 PM IDT)
*Chu-Wee Lim (14/4/2021 7:32 PM IDT)
*David Greer (16/4/2021 10:08 PM IDT)
Hans Kodde (16/4/2021 10:19 PM IDT)
*Shouky Dan & Tamir Ganor (18/4/2021 5:58 PM IDT)
*Amos Guler (18/4/2021 8:47 PM IDT)
Fabio Michele Negroni (18/4/2021 9:36 PM IDT)
*Joaquim Carrapa (19/4/2021 12:21 AM IDT)
*Radu-Alexandru Todor (19/4/2021 11:09 AM IDT)
*Nyles Heise (21/4/2021 6:05 AM IDT)
*Gundars Kokts (21/4/2021 8:29 PM IDT)
*Tomer Vromen (24/4/2021 2:11 PM IDT)
*Benjamin Lui (25/4/2021 5:58 PM IDT)
Hansraj Nahata (26/4/2021 6:16 AM IDT)
*David Friedman (27/4/2021 2:49 AM IDT)
*Imane Kebbaj (27/4/2021 8:23 PM IDT)
*Todd Will (28/4/2021 12:18 AM IDT)
Jonathan Martin (28/4/2021 3:46 PM IDT)
*Motty Porat (28/4/2021 11:59 PM IDT)
*Albert Stadler (29/4/2021 8:00 PM IDT)
*Andrea Andenna (30/4/2021 12:24 AM IDT)
*Kang Jin Cho (30/4/2021 7:31 AM IDT)
*Andy Greig (30/4/2021 7:51 AM IDT)
Sammy El Khammal (30/4/2021 8:42 AM IDT)
*Li Li (30/4/2021 11:59 PM IDT)
Sumanth Ravipati (1/5/2021 5:31 PM IDT)
*Govind Jujare (1/5/2021 11:30 PM IDT)
*Oscar Volpatti (2/5/2021 9:28 AM IDT)
*James Muir (3/5/2021 6:36 AM IDT)