Can You Solve These Challenging Riddles and Win a Prize?

[mfb]

4. I'd wish to go first. The only thing the first player needs to do is pick the bottom coin no matter what the second player does. Doing this will result in player one always removing the last stack. I see it has been solved already, but I like riddles.

For the first move it doesn't matter what the second player does because the second player is the second player. Afterwards the first player has to take into account what the second player did to continue.

#3. Riddle: You want the person 3 places standing counterclockwise before you to begin the process, wherever you are located as the leader. So if you are in place number 50, you want to select #47 to die first.

Then you die quickly.

 

[CynicusRex]

For the first move it doesn't matter what the second player does because the second player is the second player. Afterwards the first player has to take into account what the second player did to continue.

Edited; incorrect again.

 

[jkxzgyk]

For number 3:
With 1000 (or any even number) sect members, start with the person one place on from yourself (ie. if members numbered 1-1000 clockwise starting with you as #1, then have #2 die first). This will kill all even numbered members until reaching #1000, at which point it loops back, misses you, and starting with #3 kills all other odd numbers leaving #1 (you) as the last one alive. If instead there were an odd number of members then start one place back from yourself, eliminating the extra number before starting one place ahead of you and functioning as if it were an even number of members.

How I worked it out: Tried up to ten members and then worked out the pattern

 

[mfb]

It doesn't work with 10 members either, you kill 2 4 6 8 10 3 7 and then yourself.A general comment on games like #4 and #5, where both players know the state of the game, and have the same options to move, and the game ends after a finite number of moves: Every possible state can be classified as "you can enforce to win the game" or "the other player can enforce to win the game". You can classify all states if you start from the end.

As an example, consider the game where you win if the number reaches 100, and you can add 1 to 10 to the number: if it is your turn, all numbers 90 to 99 are "you can enforce to win the game" (short: winning position) because you can directly go to 100. What about 89? No matter what you add, you will always leave a "the next player can win the game" situation for the opponent, so 89 is a "the other player can enforce to win the game", or short: a losing position. What about 79 to 88? If you go to 89, the opponent has a losing position. If you go to anything else, the opponent has a winning position (because they can then go to 89), which means you gave away your advantage.

This can be generalized: a losing position is a position where all possible moves go to a winning position, or where it ends the game by losing. A winning position is a position where at least one possible move goes to a losing position, or where it ends the game by winning.

Typically most positions in a game are winning positions, because the condition for it is much weaker. That also means most moves go to a winning position - if you have a winning position you have to be careful to always give your opponent a losing position, otherwise the opponent can win and you can do nothing against it.

The task is now to classify all losing positions.

 

[jkxzgyk]

It doesn't work with 10 members either, you kill 2 4 6 8 10 3 7 and then yourself.

Welp, time to try again then :P

 

[CynicusRex]

4. I'd wish to be the first player. For P1 to win he or she needs to make an even number of coins to win. If he does not, P2 can win. I reduced the problem to 3 rows with 2 coins so it is similar to the riddle, but simpler. Thanks for trying to read my handwriting.

So, from the moment any of the players makes an uneven amount of coins on their turn, they give the win to their opponent; assuming the opponent keeps an even amount of coins.

 

[PeroK]

4. I'd wish to be the first player. For P1 to win he or she needs to make an even number of coins to win. If he does not, P2 can win. I reduced the problem to 3 rows with 2 coins so it is similar to the riddle, but simpler. Thanks for trying to read my handwriting.

So, from the moment any of the players makes an uneven amount of coins on their turn, they give the win to their opponent; assuming the opponent keeps an even amount of coins.

Do you think in general an odd number of coins is always winning?

what about distinguishing between even numbers that win and lose?

Try looking at a 1,2,3 game. Then 1,2,3,4.

 

[CynicusRex]

If there is an odd number of stacks; the first player to pick his coin resulting in an even amount of total coins, will win if he keeps the total amount of coins even on his turn.

I am afraid I do not understand what you mean by "looking at game 1,2,3"

 

[mfb]

With just two coins per stack, you don't capture the general problem. "even number of coins" is directly equal to "even number of stacks with exactly 1 coin" in your smaller problem, those two are not identical in the original problem.

Also, here is a proof that your algorithm cannot be generalized. Take 4 stacks of 2 coins each. What does the first player do to guarantee an even number of coins? Take away one stack. But now we are in a situation where you expect the other player to win.

 

[CynicusRex]

So it must be generalized for every possible amount of stacks and coins?

 

[PeroK]

If there is an odd number of stacks; the first player to pick his coin resulting in an even amount of total coins, will win if he keeps the total amount of coins even on his turn.

I am afraid I do not understand what you mean by "looking at game 1,2,3"

A game with three stacks, one with 1 coin, one with 2 coins and one with 3 coins.

 

[RUber]

For number 3:
So if position p is first to go, you want to be in position p+975.

To confirm my findings, I built a brute-force method to check. Below is the MATLAB code to simulate the scenario in Riddle #3. Position p+975 (or p-25) is the best place to be standing.

function Answer = Riddle2(N)
%given starting number N, riddle starting with 1. 
S = [1:N]';
S2 = [S, S];
clear S

k = 1;
while k < length(S2)
if mod(k,2)==1
S2(k,2) = 0;
else
S2 = [S2;[S2(k,1),S2(end,2)+1]];  %append surviving person to end of list
end

k = k+1;
end

Answer = S2(end, 1);
fprintf('If first to go is #1, you want to stand in position %g', Answer)

[\code]

 

[mfb]

So it must be generalized for every possible amount of stacks and coins?

At least general enough for the initial puzzle, 5 stacks of 1000 coins. There are some states that will never be reached if the first player plays optimal.

There is a more general solution that works for arbitrary starting positions that has not been posted yet.

 

[m k]

And so on. Filling out the table up to 5 Euro and 2 Euro coins leads to N_all(500) = 390724750

Is the note included?

 

[Orodruin]

Alternative solution for 3 which will work for any number N of sect members:

Count backwards! You are last. Before the last lap, there was two people, you and the other. Before the second to last, there were four. Before the nth to last, there were $2^n$. Of course, one of the laps (the first) is not full unless N is a power of two. Find the largest power of two and then distribute the surplus between the people killed in later laps.

For the case of N = 1000: $2^9=512$, leaving 488 victims to be distributed. If you are at position 1, victim k goes in position 2k, ie, you start at position 976 (and then go in the direction of decreasing numbers).

This is compatible with RUber's answer (but counting the other direction).

Edit: So in the general case: Let $m$ be the largest integer such that $2^m < N$. Then the first victim should be chosen as $2(N-2^m)$ if you are in position 1.

Edit 2: Fixed parentheses.

 

[CynicusRex]

At least general enough for the initial puzzle, 5 stacks of 1000 coins. There are some states that will never be reached if the first player plays optimal.

There is a more general solution that works for arbitrary starting positions that has not been posted yet.

Mistake found, again. The riddle sounds easier than it is.

 

[Pro7]

I think the leader should stand at position 768 from the person he chooses in the clockwise direction .

 

[geminiinspace]

Then you die quickly.

Huh?

I guess riddles aren't for me.

 

[Orodruin]

I think the leader should stand at position 768 from the person he chooses in the clockwise direction .

If you had read the rest of the thread, you would know that this is wrong.

 

[votingmachine]

The coin problem. Go first and win. You can win if after your move there are two piles with an equal number in them. So two piles with one coin remainng after your move forces the other player to remove a coin/pile, and you remove the winning coin. If there remains a pile with a single coin, and one with 2 coins (or any number more), the other player removes the top to leave two pile of a single coin, and wins.

IE,if after player A takes a coin, there remains:
pile 1 ... pile 2
1 . . . . . . 1 Player A wins (B takes a coin/pile, and then A takes the last one to win)
1 . . . . . . 2 Player B takes one coin leading to the first situation with player B winning.
1 . . . . . . 2+ Player B takes the coins leaving the single coin situation.
2 . . . . . . 2 Player A wins. Player B cannot clear either pile or he loses. If he takes one coin, he leaves the losing situation of 1 coin and 2 coins.
2 . . . . . . 3 Player B wins. Take one coin and the situation is the prior one
2 . . . . . . 3+ Player B wins by taking enough coins to leave 2 stacks of 2 coins each.
3 . . . . . . 3 Player A wins. If B takes one coin, that leads to the 2 coin and 3 coin problem. If B takes 2 coins, that leads to the 1 coin and 2+ coin problem.
3 . . . . . . 4 Player B wins. Take one coin, and then it is the winning situation of 3 and 3.
3 . . . . . . 4+ Player B wins. Take enough coins to be at 3 and 3.
4 . . . . . . 4 Player A wins. B's move leaves it at 3 and 4, 2 and 3+, or 1 and 2+ ... all losing positions.
I extended this further, but won't re-type it.

The goal is then to not reach a two pile state with an equal amount in the piles. Extending further back, the same reasoning applies to 4 piles. If one player can force two pairs of piles with equal numbers after their move, they can win. Say there are two piles with 1 coin and two piles with 3 coins after your move. The situation can be played as two independent pairs, both with the winning strategy for the player who left that situation. If B removes a 1 coin pile, do the same. Then it is 3 and 3. If B takes a 3 coin pile or a coin from a 3 coin pile, take the same thing

So moving first, take an entire pile, leaving two pairs of equal coin amounts. Then simply exactly mimic the 2nd players removals, to always keep the remaining piles as two equal amounts.

 

[votingmachine]

The suicide cult problem. If I arrange a circle with 3-1-2 as the final 3, the third last killed is at 3, then 1 is skipped and the 2nd last killed is at 2 (think of a clock with 1 at 12 o'clock, 2 at 4 o'clock, and 3 at 8 o'clock) . The 4th to last killed is then between 2 and 1 (call it at 2 o'clock), killed, then skipping 2, to go thru 3-2-1. The 5th is between 3 and 1, killed, then skip 1, to get to 4, then etc. As I keep adding the dead successively, with a spacer person in between them and the next lower number, I notice that the person to the left of the last one killed is always 2^n. It starts with the #2 to last dead. Then the #4 to last dead was placed there. Then the #8. Then the #16.

512 is the largest 2^n less than 1000. So the 512th to last person killed must be immediately clockwise from the leader. The 513th is to the counter-clockwise side. the next 487 prior to that must be every other person, so another 974 counterclockwise around the circle. Starting with the 975th person counterclockwise to myself, the other 999 will die before me. That is also the 24th person located clockwise to myself.

 

[CynicusRex]

So moving first, take an entire pile, leaving two pairs of equal coin amounts. Then simply exactly mimic the 2nd players removals, to always keep the remaining piles as two equal amounts.

Seems legit to me.

 

[votingmachine]

Oops. I did not see RUber's already answered that one.

 

[mfb]

Is the note included?

The note was not mentioned in the puzzle, so I did not include it. There are also 5 Euro coins (with a glowing blue ring), but you don't see them in circulation.

micromass, can you remove me from puzzle 1? I knew it before, and I don't think I wrote anything new in my post.

 

[PeroK]

Alternative solution for 3 which will work for any number N of sect members:

Count backwards! You are last. Before the last lap, there was two people, you and the other. Before the second to last, there were four. Before the nth to last, there were $2^n$. Of course, one of the laps (the first) is not full unless N is a power of two. Find the largest power of two and then distribute the surplus between the people killed in later laps.

For the case of N = 1000: $2^9=512$, leaving 488 victims to be distributed. If you are at position 1, victim k goes in position 2k, ie, you start at position 976 (and then go in the direction of decreasing numbers).

This is compatible with RUber's answer (but counting the other direction).

Edit: So in the general case: Let $m$ be the largest integer such that $2^m < N$. Then the first victim should be chosen as $2(N-2^m)$ if you are in position 1.

Edit 2: Fixed parentheses.

If you are in position 1, then the first victim must be as position:

$2^{m+1} +2-N$

E.g. $N = 1000$, first victim at $26$

This equates to first victim at $1$ you need to be at $976$.

You need to be at position $2(N-2^m)$ if the first victim is at position 1.

 

[Orodruin]

If you are in position 1, then the first victim must be as position:

$2^{m+1} +2-N$

E.g. $N = 1000$, first victim at $26$

This equates to first victim at $1$ you need to be at $976$.

You need to be at position $2(N-2^m)$ if the first victim is at position 1.

This depends on the direction you count in. I specifically stated I count in the direction of lower numbers. Your solution counts the other way.

 

[PeroK]

This depends on the direction you count in. I specifically stated I count in the direction of lower numbers. Your solution counts the other way.

Sorry, I missed that. Yours was a very neat solution in any case.

 

[CynicusRex]

So #4 hasn't been solved by Votingmachine?

 

[micromass]

Yep, he did solve it.

So the winners are:
mfb
RUber
Orodruin
PeroK
votingmachine
fresh_42
Zarqon
martinbn

I will ask @Greg Bernhardt to choose one of these who wins the prize. Thank you all for playing!

 

[Orodruin]

You can remove me from contention. Apart from looking rigged if a mentor would win, the thought process itself is enough reward.

 

[Greg Bernhardt]

I assigned each member a number and then ran a random number generator. @RUber wins!

 

[Orodruin]

I assigned each member a number and then ran a random number generator. @RUber wins!

Congratulations @RUber , well deserved.

 

[RUber]

Thanks!

 

[PeroK]

Just an afterthought for #3 to avoid counting backwards. I'll do it with $N = 11$ members, so that $2^m = 8$. And we want position 1 to survive.

First note that for $8$ members, you will survive by starting at $2$

$1, 2, 3, 4, 5, 6, 7,8$

The evens go first, then the odds (3,7,5). As long as N is a power of 2, position 1 survives.
You need to place the remaining three members so that they go first, followed by $2$. So you do:

$1, 2,3,4,5,6,X1,7,X2,8,X3$

And start with $X1$.

In general, $X1$ will be in position:

$N - 2(N-2^m) +2 = 2^{m+1}- N +2$

 

[jedishrfu]

If it wasnt mentioned earlier the 1000 people circle is a variation of the Josephus problem. Josephus proposed this among his leaders rather than surrender to the Romans as it was forbidden to take your own life you were to instead kill the one next to you.

In the end, only Josephus was left standing, subsequently captured by the Romans and he then aided them in putting down the Jewish revolt.

As a reward, he was freed and became the one to chronical the history of the time. The two Roman generals, father and son both ascended to Roman emperors Vaspasian and Titus.

It was always suspected that he rigged the game knowing the best place to stand ie he selected the first player to start the game.

The moral of the story is knowing the right math can save your life.

https://en.wikipedia.org/wiki/Josephus