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

[micromass]

Below are $6$ riddles. Everybody completing a riddle has a chance on winning the book "Dark Matter and the Dinosaurs".

Rules:

• For an answer to count, the complete reasoning must be given, not just the answer.
• Do not answer a question you already know the answer to.
• If a question is already solved, you can still obtain recognition by generalizing the question!

1. SOLVED BY mfb I have two buckets, one which can contain $p$ liters of water, and one which can contain $q$ liters of water. Both $p$ and $q$ are integers. You have access to a river with unlimited amount of water. You are asked to give the King $n$ liter water. You have no other buckets. For which $n$ is this possible? Detail the steps I need to take to complete this.
2. SOLVED BY mfb In the euro system, you have coins of $1$ cent, $2$ cents, $5$ cents, $10$ cents, $20$ cents, $50$ cents, $1$ euro (= $100$ cents) and $2$ euro. I am asked to pay $5$ euros. In how many different ways can I do this?
3. SOLVED BY RUber, Orodruin, PeroK, votingmachine I am the leader of a sect with $1000$ people (including me). I have recently declared that the entire sect should commit suicide. The entire sect stands in a circle. I point out somebody who is to commit suicide. After this we move clockwise and every second remaining person commits suicide. At which place should the leader stand in order to survive the suicide and obtain all the riches from the members? For example, if there were only $5$ members named $1$, $2$, $3$, $4$, $5$ and I say that $3$ kills himself first, then $5$ will go, then $2$ and finally $1$. The leader should be at place $4$.
4. SOLVED BY votingmachine I have $5$ piles of $1000$ coins. There are two players. Player $1$ begins and chooses a coin. That coin is then removed and all the coins above it are removed too. Player $2$ does the same. Etc. The player who removes the last coin wins (as the other player cannot remove any coin). Do you wish to go first or second?
5. SOLVED BY fresh_42, PeroK Two players start from $0$ and alternatively adds $1$ to $10$ to the sum. The first who reaches $100$ wins. Do you want to go first?
6. SOLVED BY Zarqon, martinbn 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?

Thank you! I hope everybody will like these questions! Please provide any feedback you wish!

 

[fresh_42]

5. Two players start from $0$ and alternatively adds $1$ to $10$ to the sum. The first who reaches $100$ wins. Do you want to go first?

Yes, because I want to be the first who reaches 1. Reason: The first who reaches 89 cannot be beaten, since the other one can't reach 100 but has to add at least 1. So recursively the first at 78, 67, 56, ... , 12, 1 will win, which can't be the one who chooses second.

 

[Pepper Mint]

1. I have two buckets, one which can contain $p$ liters of water, and one which can contain $q$ liters of water. Both $p$ and $q$ are integers. You have access to a river with unlimited amount of water. You are asked to give the King $n$ liter water. You have no other buckets. For which $n$ is this possible? Detail the steps I need to take to complete this.

Supposing p<q

if p>n
   Choose p to make n
if p<n<q
   Make n liters of water from p and q buckets
if p<q<n
then
    if p+q>n
         Make n liters of water from p and q buckets
    else if p+q<n
         You get executed by the King then

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?

Just feel free to be ready for one thirds.
One of the three people has to show some politeness by e.g accepting the first piece that is cut. Then we divide the rest in half. Certainly three pieces may not be perfectly equal 1/3 the cake but halving is always producing a better result. You can trim the piece from the first person for one of the two if you mis-cutting the remaining large piece while not making the first guy sad.

 

[micromass]

Yes, because I want to be the first who reaches 1. Reason: The first who reaches 89 cannot be beaten, since the other one can't reach 100 but has to add at least 1. So recursively the first at 78, 67, 56, ... , 12, 1 will win, which can't be the one who chooses second.

Nice!

 

[JorisL]

For number two, do we have to keep in mind that the receiving party can legally decline payment with more than 50 coins? [article 11 of http://eur-lex.europa.eu/LexUriServ/LexUriServ.do?uri=OJ:L:1998:139:0001:0005:EN:PDF ]

 

[micromass]

For number two, do we have to keep in mind that the receiving party can legally decline payment with more than 50 coins? [article 11 of http://eur-lex.europa.eu/LexUriServ/LexUriServ.do?uri=OJ:L:1998:139:0001:0005:EN:PDF ]

You can try to solve both

 

[JorisL]

Maybe next week when I've got some time to waste :-D

 

[PeroK]

Yes, because I want to be the first who reaches 1. Reason: The first who reaches 89 cannot be beaten, since the other one can't reach 100 but has to add at least 1. So recursively the first at 78, 67, 56, ... , 12, 1 will win, which can't be the one who chooses second.

To generalise. The player who chooses first has a winning strategy unless the total target is a multiple of 11.

 

[Zarqon]

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?

Hmm, first wrote some more advanced strategy with different orderings of cuts and choosings, but now I think a simple solution is better:

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.(maybe I'm missing some underlying assumption about this riddle, since the solution seems ways simpler than the other riddles)

 

[martinbn]

1. Euclid's algorithm, so multiples of gcd(p,q).

6. 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.

 

[fresh_42]

1. Euclid's algorithm, so multiples of gcd(p,q).

That's been my first thought, too. But the difficulty is: you quickly run out of buckets! No bucket to store results in between.

 

[Ibix]

1. I have two buckets, one which can contain $p$ liters of water, and one which can contain $q$ liters of water. Both $p$ and $q$ are integers. You have access to a river with unlimited amount of water. You are asked to give the King $n$ liter water. You have no other buckets. For which $n$ is this possible? Detail the steps I need to take to complete this.

Without loss of generality, I shall assume that $p<q$ for the purpose of this answer.

$n=0$, $p$, $q$ and $p+q$ are trivial - fill neither, one, or both.

$n=Np$, where $n\leq q+p$ is possible by filling $p$ and emptying it into $q$, $N$ times, and optionally filling $p$ a final time.

$n=q-Np$, where $n\leq q$ is possible by filling $q$, then filling $p$ from $q$ and discarding the water in $p$ $N$ times, keeping what remains in $q$.

$n=Np-q$, where $Np\geq q\geq (N-1)p$ is possible by filling $p$ and emptying it into $q$, stopping when $q$ is full and keeping what remains in $p$. You can then empty $q$, transfer the water from $p$, and add any multiple of $p$ up to a total volume not exceeding $q$ by repeatedly filling $p$ and emptying it into $q$. You can also add an additonal $p$ by filling $p$.

Some solutions are degenerate, depending on the common factors of $p$ and $q$.

Any integer multiple or combination of these can be achieved with multiple trips.

In summary, $n=Np$, $n=q-Np$ and $n=Np-q$ are all possible, subject to the restrictions that $N$ is a non-negative integer and $n\leq p+q$.

 

[mfb]

That's been my first thought, too. But the difficulty is: you quickly run out of buckets! No bucket to store results in between.

You don't need any storage. Every multiple of gcd(p,q) can be written as c*p+(a*p-b*q) with positive a, b where (a*p-b*q)<p . Start giving the king c*p water, then focus on the fractional part: Fill the p container, empty it into the q container until it is full, throw q water away, repeat until p container is empty, fill p container again, ... every time you fill p you increase the sum of water in your buckets by p, every time you empty q you reduce it by q, until you hit n*p-m*q, the remaining water the king needs.

If you want to directly hand the king the water in the two buckets, you are limited to the sum p+q, of course.

Edit@Ibix: You are missing solutions, e.g. give 3 liters of water with buckets of 7 and 8. Fill 8 from river, use it to fill 7 (now 1 liter in 8), discard 7, fill 8 from river, use it to fill 7, discard 7 (now 2 liter in 8), repeat one more time to get 3 liters.

n=Np-Mq are all possible. Which is every multiple of the largest common denominator.Problem 2: Do it coin by coin, I'll work without limits on the number of coins.
With 1 cent coins only, there is always N₁(x)=1 option to pay x cents.
With 2 cents, I have N₁₂(x)=N₁(x)+N₁₂(x-2) options to pay any amount.
With 5 cents, I have N₁₂₅(x)=N₁₂(x)+N₁₂₅(x-5) options to pay any amount.
And so on. Filling out the table up to 5 Euro and 2 Euro coins leads to N_all(500) = 390724750Can we link those riddle threads at some place with a new post per thread, so it is possible to watch them easily? I like them, but they can be hard to find.

 

[Ibix]

every time you fill p you increase the sum of water in your buckets by p, every time you empty q you reduce it by q, until you hit n*p-m*q, the remaining water the king needs.

Neat. It's not my day for these things, obviously...

 

[RUber]

For number 3,
Assume you start with person #1, then the first round of suicides takes out all the odds.
On the next round, there are 500 people, with even original numbers 2k for k = 1 to 500. The suicides take out odd values of k.
On the next round there are 250 people with original numbers 4k for k = 1 to 250. The suicides take out odd values of k.
The following round there are 125 people with original numbers 8k for k = 1 to 125. The suicides take out odd values of k.
At this point, there are 62 people remaining with original numbers 16k for k = 1 to 62. However, 16 is skipped. The suicides take out the even values of k.
What remains are 31 people with original numbers 16(2k-1) for k = 1 to 31. The suicides take out the even values of k.
Now there are 16 people with original numbers 16(2(2k-1)-1) for k = 1 to 16. The suicides take out odd values of k.
Now 8 people remain, with original numbers 16(2(4k-1)-1). The suicides take out the odd values of k.
Now 4 people are left. Original numbers of 16(2(8k-1)-1). The suicides again take out odd values of k.
Now 2 people remain. Original numbers are 16(2(16k-1)-1) for k = 1, 2. k = 1 is first to go...leaving k = 2 for last.
Expanding, we see that the best position to be in is 16(2*31-1) = 976.
So if position p is first to go, you want to be in position p+975.

 

[geminiinspace]

I'm new here (have yet to post an introduction!), but I saw "riddles," and couldn't help but give this a try!

#4. You want to go first and maintain an even number of coins on the table when you take a turn. Mathematically this works out in your favor with there being an even number of coins and an odd number of stacks to start.

Reasoning: ...I worked this out in my head/on paper and am really struggling to express the logic without writing out all the tests and variations I imagined.

I'm very new to expressing my logical/visual understanding... I've never taken a physics or logic class, but I have natural ability and questions about education/employment...which is why I'm here! :)

 

[PeroK]

I'm new here (have yet to post an introduction!), but I saw "riddles," and couldn't help but give this a try!

#4. You want to go first and maintain an even number of coins on the table when you take a turn. Mathematically this works out in your favor with there being an even number of coins and an odd number of stacks to start.

Reasoning: ...I worked this out in my head/on paper and am really struggling to express the logic without writing out all the tests and variations I imagined.

I'm very new to expressing my logical/visual understanding... I've never taken a physics or logic class, but I have natural ability and questions about education/employment...which is why I'm here! :)

What would be your first move? How many coins would you take away?

 

[geminiinspace]

What would be your first move? How many coins would you take away?

It wouldn't matter as long as there are an even number of coins left after my turn. I could clear a stack if I wanted, or I could take an even number of coins off a stack. Either way I will still win.

 

[PeroK]

It wouldn't matter as long as there are an even number of coins left after my turn. I could clear a stack if I wanted, or I could take an even number of coins off a stack. Either way I will still win.

But if you take 2 coins, say, then I could take 2 coins from the same pile and that would be the same as you taking 4 coins first, with roles reversed. So who'd be winning then?

 

[geminiinspace]

#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.

 

[Ibix]

#4: Player 1 wins by the following strategy.

Player 1 immediately removes one column. Afterwards, whatever coins player 2 takes, player 1 takes the same from a pile of the same height as the pile 2 took from. This guarantees that there is always a column of the same height. It also guarantees that player 2 must eventually remove a column, which 1 then does too. That leaves two columns; again player 2 is eventually forced to remove a column, whereupon 1 removes the other and wins.

Fascinating game...

 

[geminiinspace]

#4: Player 1 wins by the following strategy.

Player 1 immediately removes one column. Afterwards, whatever coins player 2 takes, player 1 takes the same from a pile of the same height as the pile 2 took from. This guarantees that there is always a column of the same height. It also guarantees that player 2 must eventually remove a column, which 1 then does too. That leaves two columns; again player 2 is eventually forced to remove a column, whereupon 1 removes the other and wins.

Fascinating game...

Player 1 does not have to go to the extent to duplicate moves, they just have to maintain an even number of coins on the table and can do it in any fashion they like. They could really have fun with it and draw it out to trick Player 2. :)

 

[PeroK]

Player 1 does not have to go to the extent to duplicate moves, they just have to maintain an even number of coins on the table and can do it in any fashion they like. They could really have fun with it and draw it out to trick Player 2. :)

This is not correct. As pointed out in my earlier post. There is only one winning move to begin, as @Ibix indicates. If you take any less than the full column on your first turn, then your opponent can take the rest from that column leaving you in a losing position.

Also, if at any stage you deviate from @Ibix strategy, then your opponent can turn the tables by reestablishing the symmetry in his favour.

 

[PeroK]

#4: Player 1 wins by the following strategy.

Player 1 immediately removes one column. Afterwards, whatever coins player 2 takes, player 1 takes the same from a pile of the same height as the pile 2 took from. This guarantees that there is always a column of the same height. It also guarantees that player 2 must eventually remove a column, which 1 then does too. That leaves two columns; again player 2 is eventually forced to remove a column, whereupon 1 removes the other and wins.

Fascinating game...

The other fascinating thing is that if the game is changed so that the player who takes the last coin loses, then the the game is equivalent and the same strategy applies. Only at the end you avoid a 1, 1 scenario in favour of 1, 0. And avoid 1,1,1,1 in favour of 1,1,1, with your opponent to play.

 

[Ibix]

Player 1 does not have to go to the extent to duplicate moves, they just have to maintain an even number of coins on the table and can do it in any fashion they like. They could really have fun with it and draw it out to trick Player 2. :)

I don't think so. In addition to what @PeroK said, if 1 fails to maintain the balance after the first move, 2 can do it for her and then win by the strategy I outlined for 1.

Edit: never mind, PeroK said that too. I must learn to read...

 

[geminiinspace]

This is not correct. As pointed out in my earlier post. There is only one winning move to begin, as @Ibix indicates. If you take any less than the full column on your first turn, then your opponent can take the rest from that column leaving you in a losing position.

Also, if at any stage you deviate from @Ibix strategy, then your opponent can turn the tables by reestablishing the symmetry in his favour.

There are actually many winning moves to begin with... I have played this game outright and indeed have won without having to clear out a stack right away. :)

Example:
Player 1 removes HALF of stack 1
Player 2 clears stack 1
Player 1 clears stack 2
Player 2 clears stack 3
Player 1 can clear any number of coins (except for, obviously, a full stack, else they lose here). They can still win. Player 2 can alternate removing an even or odd amount, and it won't matter.

If you need me to draw a visual of the turns remaining, I can. It does work out. Just experiment. :)

 

[Ibix]

There are actually many winning moves to begin with... I have played this game outright and indeed have won without having to clear out a stack right away. :)

Example:
Player 1 removes HALF of stack 1
Player 2 clears stack 1
Player 1 clears stack 2
Player 2 clears stack 3
Player 1 can clear any number of coins (except for, obviously, a full stack, else they lose here). They can still win. Player 2 can alternate removing an even or odd amount, and it won't matter.

I don't think so. There are two equal stacks, numbers 4 and 5, remaining after Player 2's second go. Whatever 1 takes off one of them, 2 takes off the other. This must end with 1,1 on Player 1's go and he loses.

 

[geminiinspace]

I don't think so. There are two equal stacks, numbers 4 and 5, remaining after Player 2's second go. Whatever 1 takes off one of them, 2 takes off the other. This must end with 1,1 on Player 1's go and he loses.

I'm not sure I understand your example then. Maybe I'm just confused.

Say there are 2 full stacks remaining, and it's Player A's turn to go.

Player A can reduce stack 4 down to 1 coin.

Player B can reduce stack 5 down to 2 coins.

Player A can reduce stack 5 down to 1 coin.

Player B is now forced to clear one of the stacks and loses because Player A clears the last one.

 

[Ibix]

The other fascinating thing is that if the game is changed so that the player who takes the last coin loses, then the the game is equivalent and the same strategy applies. Only at the end you avoid a 1, 1 scenario in favour of 1, 0. And avoid 1,1,1,1 in favour of 1,1,1, with your opponent to play.

That's kind of cool, actually. Forcing a win in your game is forcing a loss in @micromass's, and you use the same strategy except for the endgame.

 

[Ibix]

I'm not sure I understand your example then. Maybe I'm just confused.

Say there are 2 full stacks remaining, and it's Player A's turn to go.

Player A can reduce stack 4 down to 1 coin.

Player B can reduce stack 5 down to 2 coins.

...or player B can reduce stack 5 to 1 coin and win because A's hand is now forced.

 

[geminiinspace]

...or player B can reduce stack 5 to 1 coin and win because A's hand is now forced.

True...but I thought the point someone was trying to make was that Player A can ONLY win if they clear a stack immediately...which simply isn't true..

 

[geminiinspace]

Maybe I just don't understand the riddle *shrugs* :)
either way, been fun talking!

 

[Ibix]

True...but I thought the point someone was trying to make was that Player A can ONLY win if they clear a stack immediately...which simply isn't true..

You are assuming cooperative play. Player 1 can only force a win if they clear a stack on the first move. If they don't do it, Player 2 can force a win from his first move by clearing the stack that 1 didn't and adopting my strategy.

 

[Orodruin]

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.

How is this fair to the person selecting second? The classical version of this riddle does not state that they should each get 1/3 of the cake, it states that all three should be satisfied with their share, i.e., get a piece which they value as at least 1/3 of the value of the total. This may include different toppings which different people value differently.

 

[CynicusRex]

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.

edit: incorrect. This is why I love riddles.

 

[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.