April 2021
 

[url]https://www.research.ibm.com/haifa/ponderthis/challenges/April2021.html[/url]

[QUOTE=Xyzzy;575043][url]https://www.research.ibm.com/haifa/ponderthis/challenges/April2021.html[/url][/QUOTE]

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.

If my understanding is correct, "seven steps" has to be replaced by "seven spins".
What do you mean?

[QUOTE=Dieter;575047]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.

If my understanding is correct, "seven steps" has to be replaced by "seven spins".
What do you mean?[/QUOTE]

I also think you are correct

[quote]On each spin, the [B]wheel[/B] moves forward q steps in a [B]clockwise[/B] direction
. . .
So, if the wheel is right before 1 and performs 3 steps, it ends up on 3.[/quote]Wouldn't it end up on 7 ("before the 1" defined as traveling over it during the spin)? If it started betwen the 8 and 1 and the wheel was rotated clockwise three steps, the arrow would end up on the 6.

[QUOTE=EdH;575144]Wouldn't it end up on 7 ("before the 1" defined as traveling over it during the spin)? If it started betwen the 8 and 1 and the wheel was rotated clockwise three steps, the arrow would end up on the 6.[/QUOTE]

Three remarks:

- See #2: seven spins, not seven steps
- The wheel turns anti-clockwise. Or the arrow turns clockwise.
- What does mean: "there is a set of unwinnable numbers"? "There is at least one set" or "there is exactly one set"?

[QUOTE=EdH;575144]Wouldn't it end up on 7 ("before the 1" defined as traveling over it during the spin)? If it started betwen the 8 and 1 and the wheel was rotated clockwise three steps, the arrow would end up on the 6.[/QUOTE]I noticed that also. As to "steps," the problem says (my emphasis)[quote]On each spin, the wheel moves forward q [b]steps[/b] in a [color=red]clockwise[/color] direction and the number / prize reached is eliminated from the wheel (i.e., the player does not get it).

Each [b]step[/b] 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.[/quote]I am unable to reconcile this usage of "steps" with the usage WRT "unwinnable sets."

I also note[quote]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).[/quote]The phrase "a little less" is ambiguous. I'm not sure whether the step size remains in constant proportion to the distance from one number to the next. If the choice of q (number of steps in a spin) is not bounded above, it would seem that the only way to insure you never land between numbers is to make the step size an irrational multiple of pi radians...

[QUOTE=EdH;575144]Wouldn't it end up on 7 ("before the 1" defined as traveling over it during the spin)? If it started betwen the 8 and 1 and the wheel was rotated clockwise three steps, the arrow would end up on the 6.[/QUOTE]

If I replace "clockwise" by "anti-clockwise" it is possible to confirm the three unwinnable sets of the example.

[QUOTE=Dr Sardonicus;575154]I noticed that also.[/QUOTE]
From the example it seems clear that the intended meaning is that the arrow moves clockwise around the wheel.
[QUOTE]I am unable to reconcile this usage of "steps" with the usage WRT "unwinnable sets."[/QUOTE]Those refer to different things with "step".
[QUOTE]The phrase "a little less" is ambiguous.[/QUOTE] I'm pretty sure the intended meaning is "infinitesimally small". That is, the phrasing is only intended to indicate which of the two sectors is the one removed, not meant to imply that any finite multiple of it would ever reach the size of a full sector.

I'm pretty sure the intended meaning is "infinitesimally small". That is, the phrasing is only intended to indicate which of the two sectors is the one removed, not meant to imply that any finite multiple of it would ever reach the size of a full sector.[/QUOTE]

That's the only interpretation making sense. Otherwise the puzzlemaster had to concretize the "a little less than one number" - 0,9999 or so. q will become very big.

[QUOTE=uau;575166]From the example it seems clear that the intended meaning is that the arrow moves clockwise around the wheel.[/quote]But it [i]says[/i] (my emphasis)[quote] A player faced with the wheel chooses some number q and starts [b]spinning the wheel[/b] k times. On each spin, [b]the wheel moves forward[/b] q steps in a clockwise direction[/quote]Perhaps they need a proofreader...

[quote] I'm pretty sure the intended meaning is "infinitesimally small". That is, the phrasing is only intended to indicate which of the two sectors is the one removed, not meant to imply that any finite multiple of it would ever reach the size of a full sector.[/QUOTE]I was merely quibbling over the length of a "step." The number of "steps" any actual mechanical "wheel of fortune" could take in one spin would be fairly limited. The condition that this is [i]fixed[/i] (q steps per spin) is unusual, but that's what the problem says. This requirement reminds me of the "problem of Josephus."

[QUOTE=Dr Sardonicus;575235]But it [i]says[/i] (my emphasis)Perhaps they need a proofreader...

I was merely quibbling over the length of a "step." The number of "steps" any actual mechanical "wheel of fortune" could take in one spin would be fairly limited. The condition that this is [i]fixed[/i] (q steps per spin) is unusual, but that's what the problem says. This requirement reminds me of the "problem of Josephus."[/QUOTE]

Indeed it is Josephus Problem.
In example 1 of the wheel with q = 5:
1 round removes the 5
2nd round remove the 3
3rd round removes the 8 and remains 1,2,3,6,7
The next round is the 7 which will jump.
....
But what I don't understand is example 2.
"a set of k numbers unwinnable"?

[QUOTE=Kebbaj;575253]Indeed it is Josephus Problem.
In example 1 of the wheel with q = 5:
1 round removes the 5
2nd round remove the 3
3rd round removes the 8 and remains 1,2,3,6,7
The next round is the 7 which will jump.
....
But what I don't understand is example 2.
"a set of k numbers unwinnable"?[/QUOTE]
„There are no unwinnable sets for n smaller than 9“. An example:

n=8, k=4=number of spins. When the player chooses a number q and makes 4 spins, he gets a combination of 4 different numbers between 1 and 8. When he chooses another q, he gets perhaps another combination - or the same combination.
There are (8 choose 4) = 70 such combinations. All are reachable, if you ckeck enough values for q.
But:
Example n=9 und k=4. There are 126 possible quintetts of values. But this time, only 123 of these values are reachable - (1,2,5,8,9) and (2,3,4,5,8) and (2,5,6,7,8) are not reachable. Just for fun I checked 1<=q<=10000000 - no chance .
These three combinations are "unwinnable sets".

In the challenge sometimes k is the number of spins and sometimes k is the number of elements in the remaining sets. For the number of possibilities that doesn‘t make a difference, because (n choose k) = (n choose (n-k)).
For comparing: If my code works correctly, to get the 123 in example 2 I need more than 400 as limit for q.

[QUOTE=Dieter;575261]„There are no unwinnable sets for n smaller than 9“. An example:

n=8, k=4=number of spins. When the player chooses a number q and makes 4 spins, he gets a combination of 4 different numbers between 1 and 8. When he chooses another q, he gets perhaps another combination - or the same combination.
There are (8 choose 4) = 70 such combinations. All are reachable, if you ckeck enough values for q.
But:
Example n=9 und k=4. There are 126 possible quintetts of values. But this time, only 123 of these values are reachable - (1,2,5,8,9) and (2,3,4,5,8) and (2,5,6,7,8) are not reachable. Just for fun I checked 1<=q<=10000000 - no chance .
These three combinations are "unwinnable sets".[/QUOTE]

Frankly, it is you dieter who should write the challenge, I understand perfectly the example 2, and I found all the combinaisons :
"70 combinations for the 8".
"126 possible quintetts of values"
(1,2,5,8,9) (2,3,4,5,8) (2,5,6,7,8). Not reachable.
Now i am in the process of resolving the question. !

..
Thanks.

[QUOTE=Kebbaj;575353]Frankly, it is you dieter who should write the challenge, I understand perfectly the example 2, and I found all the combinaisons :
"70 combinations for the 8".
"126 possible quintetts of values"
(1,2,5,8,9) (2,3,4,5,8) (2,5,6,7,8). Not reachable.
Now i am in the process of resolving the question. !

..
Thanks.[/QUOTE]
I only repeated this part of the challenge with other words. If A explains anything to C and B explains the same matter using other words, B always has an advantage to be understood!
I admire the puzzlemasters for their ideas.

[QUOTE=Kebbaj;575253]Indeed it is Josephus Problem.
In example 1 of the wheel with q = 5:
1 round removes the 5
2nd round remove the 3
3rd round removes the 8 and remains 1,2,3,6,7
The next round is the 7 which will jump.
....
But what I don't understand is example 2.
"a set of k numbers unwinnable"?[/QUOTE]

You are right dieter, having this advantage here of reexplaining in more detail is an additional advantage that you did not have. Sometimes I understand very quickly, and sometimes my brain crashes.
This time it's google translate which played a trick on me. By translating into French.
Wrong translation:
"he will not be able to win exactly this set after n-k spins.
"il ne pourra pas gagner exactement cet ensemble après nk tours"

nk: 9 * 5 = 45 turns that blocked me. And I did not reread the English version. ( je sents mieux les choses en Français).

I know that if I block the first day of the puzzle, it's gone for a total block.

visualization of example
 

josephus problem
I made a video visualization of example 1:

[url]https://youtu.be/vdRDmy_tou4[/url]

Ok:smile:

Nice.

But man, didn't you find a larger font? And more red? :razz:
(it really hurt the eyes to read that!)

0[QUOTE=LaurV;576062]Nice.

But man, didn't you find a larger font? And more red? :razz:
(it really hurt the eyes to read that!)[/QUOTE]

Hahaha
For the red, I would have liked you to see it in green !. But presbyopic peoples are very rare !!
:le sourire:

Confused about the bolded part: "Your goal: Find an n such that there is a set of unwinnable numbers for [B]seven steps (i.e., the set is of size n-7)[/B]. In your answer, supply the number n and the elements of the unwinnable set." So are the amount of steps and the amount of spins both equal to 7? Or did they mean that there are 7 spins and q can be any value we find that results in at least 1 unwinnable set?

[QUOTE=Yusuf;576706]Confused about the bolded part: "Your goal: Find an n such that there is a set of unwinnable numbers for [B]seven steps (i.e., the set is of size n-7)[/B]. In your answer, supply the number n and the elements of the unwinnable set." So are the amount of steps and the amount of spins both equal to 7? Or did they mean that there are 7 spins and q can be any value we find that results in at least 1 unwinnable set?[/QUOTE]
Look at #2! That was my first comment.

[QUOTE=Yusuf;]


The amount of steps and the amount of spins both equal to 7? No.


The amount of steps is = 7 .
The amount of spins is a variable.

[QUOTE=Kebbaj;576761][QUOTE=Yusuf;]


The amount of steps and the amount of spins both equal to 7? No.


The amount of steps is = 7 .
The amount of spins is a variable.[/QUOTE]

But it says "the set is of size n-7", wouldn't that mean that there are 7 spins since there are 7 numbers being taken away from the wheel?

[QUOTE=Yusuf;576792][QUOTE=Kebbaj;576761]

But it says "the set is of size n-7", wouldn't that mean that there are 7 spins since there are 7 numbers being taken away from the wheel?[/QUOTE]

Yes. I'm sure that Kebbaj wanted to say this.

I repeat: Look at #2! That was my first comment to this challenge.

Or look at #8 (uau): "Those refer to different things with "step".

Seems that when the puzzlemaster formulated the real task ("your goal...") he had forgotten the definitions he had made at the beginning of the challenge.

"At each spin ... a number is eliminated from the wheel."

For the challenge without *, k=number of spins = 7.

Here's my solution. Just pretty straightforward brute force - enough for the sizes asked for in the question.

The program takes the size as input, so calling it with an argument of "7" gives the basic solution, "8" bonus one.

[CODE]#!/usr/bin/python3

from itertools import combinations
from math import lcm
import sys

def calc(n, q, s):
a = list(range(1, n+1))
for _ in range(s):
w = (q-1) % len(a)
a = a[w+1:] + a[:w]
a.sort()
return tuple(a)

turns = int(sys.argv[1])
for n in range(turns, 100):
print("Trying", n)
s = set()
for i in range(lcm(*range(n-turns+1, n+1))):
s.add(calc(n, i, turns))
r = s.symmetric_difference(set(combinations(range(1, n+1), n-turns)))
if r:
break
print(n)
print(len(r))
print(sorted(r))

[/CODE]