Challenge Can You Solve These Challenging Riddles and Win a Prize?

[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

 

[micromass]

The game with the coins is called nim. It has a very deep and interesting theory: https://en.wikipedia.org/wiki/Nim A very neat introduction to this and other games can be found here: http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf

 

[jack action]

I'm late in the game as I don't come in this section often, but I don't feel a good answer has been given for #6:

Dividing a cake fairly between two people is easy: let one person cut the cake in two pieces, let the other choose one of the pieces. How would you divide a cake fairly between three people?

• Person 1 cuts the cake into 3 pieces (each of the 3 pieces should satisfy him/her equally);
• Person 2 chooses 2 pieces (each of the 2 pieces should satisfy him/her equally);
• Case 1: Person 3 chooses 1 piece from person 2;
• Case 2: Person 3 chooses the piece from person 1, then person 1 chooses 1 piece from person 2.

This will ensure that everyone can choose what he/she consider a satisfying piece of the cake between the 3 available pieces, size-wise and/or quality-wise.

The «winning» solutions aren't satisfying, especially if we consider that 2 persons could conspire against the other one:

Let one person cut the cake in three pieces, the other two pick first, and the one who cut gets the remaining piece. The only way for the cutter to maximize his piece to 1/3 of the cake, is to cut it fairly, since any other cut than three 1/3 pieces will always leave him with a smaller piece.

This is not necessarily fair because the third person can only choose between 2 choices (whatever the second person did not choose). So person 1 could decide to make a very large piece and 2 small ones, agree with person 2 to pick the large one and person 3 is stuck with a choice between 2 small pieces such that the others share the large piece and one small piece together.

One cut what he thinks is a 1/3, if the other two are happy, it's his part and the problem is reduced to two people. If one of them is not happy he cuts a piece of the "1/3" of the first person to make it what he, the second person, thinks is a 1/3, if the third person is happy the second takes the piece and the problem is reduced to two people. If the third person is not happy cuts a what he thinks is a third and the problem is reduced to two people.

Although this may work size-wise, it is kind of messy if the second and third persons both cut a piece of the first "1/3". How do we decide who gets to keep the two small pieces to «complete» their share? To fairly do it, I guess one of the remaining person would have to cut each of the 3 remaining pieces in 2 parts and the other one would choose 1 part from each piece. We now have 7 pieces in total. Really messy.

 

[mfb]

especially if we consider that 2 persons could conspire against the other one:

That is still possible in your approach: if 1 makes one piece very good, 3 can pick it, and 2 cannot get it.

 

[jack action]

That is still possible in your approach: if 1 makes one piece very good, 3 can pick it, and 2 cannot get it.

You're right. Then I guess someone will have to eat a multi-piece share!