Milk

Alice and Bob encountered a stall selling chocolate milk--their favorite! However, they only have enough money to buy one drink and share. In front of them are 10 cups of milk arranged in a row, and each of them is assigned a value--the higher the value, the higher the temperature:

1 , 3 , 3 , 7 , 9 , 1 , 8 , 4 , 5 , 2. 1, \, 3, \, 3, \, 7,\, 9, \, 1,\, 8, \, 4, \, 5,\, 2.

The problem arises when Alice wants the milk to be as warm as possible, but Bob wants it to be as cold as possible. So, they will play a game to decide which cup of milk they will buy. They will play alternately, and Alice will go first. The process for each player is as follows:

  1. Remove 3 consecutive cups from the table.
  2. Merge the rest of the cups without changing the order.

The game ends when there is only 1 cup left, and they will buy it. Assuming that both Alice and Bob play optimally, what is the temperature of the milk they will buy?


The answer is 7.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Christopher Boo
Oct 16, 2016

No matter how they pick, only the 1 st , 4 th , 7 th , 1 0 th 1^\text{st}, 4^\text{th}, 7^\text{th}, 10^\text{th} can be the last cup of milk. This is because the numbers of cups on their left and right is divisible by 3, hence can be removed.

This problem reduces to fighting over 4 cups with temperature - ( 1 , 7 , 8 , 2 ) (1, 7, 8, 2) . Alice play first, and since she wants her milk to be as warm as possible, she removes the milk with temperature 1 1 . Then Bob removes the milk with temperature 8 8 . Finally, Alice removes the milk with temperature 2 2 and all they left is the milk with temperature 7 7 .

This is a good start. However, your explanation has a slight gap

  1. I agree that only cups 1, 4, 7, 10 can be left behind. However, in your solution, you made the slight assumption that the sequence of cup removal does not depend on the specific cups chosen. If we were only picking 1 cup each time, then this is obvious. However, since we're picking 3 cups and merging, this step needs to be elaborated on.

Keep writing more solutions and you will get the hang of this!

Calvin Lin Staff - 4 years, 8 months ago

@Christopher Boo , @Calvin Lin I have not understood 1,4,7,10 concept. Can anyone please explain me more.

Krishna Chaitanya Marreddy - 4 years, 7 months ago

Log in to reply

So my claim was only 1, 4, 7, 10 can be the last cup of milk. No matter how you remove the cups, you cannot end up with 2 as the last cup. The reason is that there is no way for you to remove the first cup while not removing the second cup. Same argument to the other cups as well.

Christopher Boo - 4 years, 7 months ago
Abdelhamid Saadi
Oct 17, 2016

This is one solution in python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def solve(cups, player):
    "Milk"
    if len(cups) != 1:
        if player== "Alice":
            return max( solve(cups[0:k] + cups[k+3:len(cups)], "Bob") for k in range(len(cups) - 2))
        else:
            return min( solve(cups[0:k] + cups[k+3:len(cups)], "Alice") for k in range(len(cups) - 2))
    else:
        return cups[0]

print (solve([1,3,3,7,9,1,8,4,5,2], "Alice"))

Can you explain what your code is doing?

Calvin Lin Staff - 4 years, 8 months ago

Log in to reply

For now It's an Minimax algorithm, later when possible, I'll add more details.

Abdelhamid Saadi - 4 years, 8 months ago
Tina Sobo
Oct 29, 2016

Alice wants the milk to be as warm as possible Looking at the initial line, the three consecutive cups with the least sum are the first three: 1, 3, 3; leaving 7 9 1 8 4 5 2

Bob wants it coldest and should remove the set of three consecutive cups with the highest sum = 9 1 8,

leaving 7 4 5 2 Alice's turn: removes the 3 with the smallest sum = 4 5 2 Leaves 7

You might be able to argue that it would be better for Bob to leave the '1' and remove a different set of 3 Say he removes 8 4 5, that leaves 7 9 1 2, which still leaves Alice with the 7.

No matter what Alice removes, in fact, Bob can take out the 9 and 8 on his turn, leaving 7 the best Alice can do. Bob can only end with colder than a 7 if he can remove the 7, 8 and 9, which would require Alice to not play optimally.

Vishwanath Kendur
Oct 18, 2016

First statement was removing 3 consecutive cups... Alice will remove the first three 1,3,3 Bob will remove 8,4,5 and we have to merge the rest. Do think of 8,4,5 you will come to know, no other consecutive options will suit for Bob. So now we are left with 7,9,1,2 Alice now will remove 9,1,2 as he wants his cup as hot as possible.

Thus we are left with only 7..

This is a good start. However, your explanation has a slight gap in explaining the reasoning:

  1. Why must Alice remove the first three 1, 3, 3? Yes, I understand that she desires to get rid of "1", so why not remove "9,1,8"?

Keep writing more solutions and you will get the hang of this!

Calvin Lin Staff - 4 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...