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.