# Tough Riddle Competition - With prize!

• Challenge

## Main Question or Discussion Point

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.
• 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!

Last edited:

fresh_42
Mentor
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.

• Delta2
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
Code:
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.

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!

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

PeroK
Homework Helper
Gold Member
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.

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)

Last edited:
• PeroK
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
Mentor
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.

• micromass
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
Mentor
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 N1(x)=1 option to pay x cents.
With 2 cents, I have N12(x)=N1(x)+N12(x-2) options to pay any amount.
With 5 cents, I have N125(x)=N12(x)+N125(x-5) options to pay any amount.
And so on. Filling out the table up to 5 Euro and 2 Euro coins leads to Nall(500) = 390724750

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

Last edited:
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
Homework Helper
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
Homework Helper
Gold Member
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
Homework Helper
Gold Member
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...

• PeroK
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
Homework Helper
Gold Member
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.

• Ibix
PeroK
Homework Helper
Gold Member
#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