9
$\begingroup$

I am a eight years old boy, I love candies, but my mom does not want me to eat any more candies because I start to have black teeth :( but I still love candies so...

Today when I was about to steal some candies from our candy box, my mom caught me! but strangely she wants to test my math skill and decided to give me a chance to get as many candies as I want if I win a game she just made up:

There are exactly 66 candies in this box, I will write all numbers from 1 to 66 to your board (1,2,3,4...,66) you will choose a number from the board and take that many candies from the box, but I will wipe that number so you will not able to take that many candies any more from the box. And also I will take candies from you to put back to the box with the left numbers written on the board as you do and wipe that number. then it is your turn etc... We will play this game until no number left on the board or no valid number of candies available to take from any of us (meaning if I have 20 candies, mom cannot try to take 21 candies from me)

If you can take the most candies from me at the end of the game, I will let you have that many candies just for today! otherwise, no candies and to your bed! Come on, tell me your first number!

Help me! I want to eat all candies,

is it possible? if not, how many can I get the most?

For the second case to end the game, I would like to clear with an example:

Let's say there are 50 candies in the candy box (mom's), and you have 16 candies: and somehow only 20,45,55 numbers are left on the board. if it is your mom's turn, she will not able to take any candies from you since the numbers on the board are bigger than the number of candies you have and the game ends there, have fun with your 16 candies :)

Improve this question
$\endgroup$
2
  • $\begingroup$ Will mom take the candies from us and put them in the original box? $\endgroup$
    – athin
    Jun 11, 2019 at 12:20
  • 1
    $\begingroup$ @athin mom takes that candies back to candy box $\endgroup$
    – Oray
    Jun 11, 2019 at 12:20

1 Answer 1

Reset to default
13
$\begingroup$

Here is one way to win almost all the candies:

Take $2$. Mom must now choose $1$, as that is the only available number less than or equal to $2$. You are left with $1$ candy.
Take $3$, giving you $4$ candies in total. Mom must now take $4$, as $1-3$ have already been played. You are left with none.

The above sequence eliminates the four lowest numbers from the board. You can however repeat the same procedure with the next four numbers (choose $6$, Mom is forced to choose $5$, choose $7$, Mom must choose $8$ leaving you with $6-5+7-8=0$).

Repeating this will eliminate all the numbers in sets of $4$, so can eliminate everything from $1$ to $64$, after which you still have no candies.
You final move is then to choose $65$. The only number on the board is $66$, which cannot be played and the game ends. You then end up with $65$ candies.

I think this solution is optimal, in the sense that you cannot end with more candies.

To get all $66$ candies, your last move must bring your total to $66$. However, as you did the first move and the number of numbers on the board is even, there must be at least one number on the board after your last move. If you had $66$ candies, all remaining numbers are valid moves for Mom, so she will be able to make a move and reduce your total. It is therefore impossible to end the game with all $66$ candies.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Beat me by a minute - have the remaining candy as a prize :o) $\endgroup$
    – GeeTee
    Jun 11, 2019 at 12:45
  • 1
    $\begingroup$ Sorry @GeeTee. Yum, candy. $\endgroup$
    – Jaap Scherphuis
    Jun 11, 2019 at 13:13
  • $\begingroup$ Can you please tell me how we can prove this by induction ?My hypothesis is that whenever there are n> 1 candies then the boy is guaranteed to get n-1 candies but not more. For instance, it is easy to see that when n =2 , the boy is guaranteed to get 1 candy but not more. When n=3, the boy is guaranteed to get 2 candies but not more, etc . What I am struggling with is the induction step. continued below . $\endgroup$
    – Hemant Agarwal
    Jul 15, 2022 at 23:31
  • $\begingroup$ Basically, how do we prove that if it is true that whenever there are n candies then the boy is guaranteed to get n-1 candies but not more then it will also be true that whenever there are n+1 candies then the boy is guaranteed to get n candies but not more ? $\endgroup$
    – Hemant Agarwal
    Jul 15, 2022 at 23:34
  • $\begingroup$ @HemantAgarwal Because the numbers can get eliminated in blocks of 4, you should write n=4k+1,2,3,4 and prove those four cases separately. I essentially proved the n=4k+2 case. For the n=4k+1 case the boy can get all n candies, which shows your hypothesis is false. For n=4k+3 (k>0) the boy gets n-2 candies. For n=4k+4 the boy also gets n-2 I think. You can use induction on m to show that any game where the numbers remaining are 4(k-m)+1 to n can be reduced to just four or fewer numbers 4k+1 to n. Then work out the best end game for each case. $\endgroup$
    – Jaap Scherphuis
    Jul 16, 2022 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.