Whiteboard

Computer Science Level 2

$1,\ 2,\ 3,\ 4,\ 5$

These five numbers are written on a whiteboard. You start with a score of 0. You pick two numbers, add their positive differences to your score, and erase your choice of one of the two numbers. This process is repeated until there is only one number left on the whiteboard.

What is the highest score you can get?

For example, if you first pick 1 and 2 and erase 2, your score becomes $2-1=1,$ and only $1,3,4,5$ are left on the whiteboard.

10 11 12 13

9 solutions

A Former Brilliant Member
Nov 12, 2017

1-Every total score we get must be a sum of 4 positive integers. (That's because every time we choose any two numbers and add their positive difference to our total score we erase one of those numbers. Since we should continue till we have erased 4 numbers, the total score would be a sum of 4 numbers)

2-During the process, we can get a score of 4 at most once, a score of 3 at most twice, a score of 2 at most three times, a score of 1 at most four times. (That's because the only two numbers you can choose to get a score of 4 are the numbers 5 and 1. Since you have to erase one of them after getting a score of 4, it's impossible to get a score of 4 twice.) (The same logic proves what we said about the score of 3, 2, 1)

Let Sn be the score we get at the nth time we choose two numbers.

S total = S1 + S2 + S3 + S4 The values of {S1, S2, S3, S4} must be chosen according to statement 2 above. So to maximize our total score we must choose a sum of 4 + 3 + 3 + 2 which is equal to 12.

You can see that a total score of 12 is possible by taking:

5 & 2 erase 2

4 & 1 erase 4

5 & 1 erase 1

5 & 3 erase 5

And that a (total score > 12) is certainly not possible according to the argument above.

# -*- coding: utf-8 -*-
"""
Created on Tue Nov 14 14:55:50 2017

@author: Michael Fitzgerald

"""
#Problem 
#https://brilliant.org/weekly-problems/2017-11-13/intermediate/?p=2
#-------

#X numbers are written on a whiteboard. You start with a score of 0. 
#You pick two numbers, add their positive differences to your score, and erase 
#your choice of one of the two numbers. This process is repeated until there is 
#only one number left on the whiteboard.   What is the highest score you can get?

#For example, if you first pick 1 and 2 and erase 2, your score becomes and only 
#are left on the whiteboard.

from math import floor

def difference(x,y,d):
    for i in x:
        for j in y:
            d = d+(j-i)
            if len(y) > 1:
                y = y[1:]
            else:
                x = x[1:]
    return x,y,d

#--------------------------------------- 

how_many_nums = 5
z = []
diff = 0

nums = []
for i in range(how_many_nums):
    nums.append(i+1)

if how_many_nums%2 == 0: 
    x = nums[:len(nums)/2]
    y = nums[len(nums)/2:]

else:
    x = nums[:len(nums)/2]
    y = nums[-int(floor(len(nums)/2)):]
    mean = sum(nums)/len(nums)
    z.append(mean)

x,y,diff = difference(x,y,diff)

if how_many_nums%2 == 1:
    z,y,diff = difference(z,y,diff)

print '\n\nThe highest score you can get with %d numbers is: %d' \
        % (how_many_nums, diff)

The highest score you can get with 5 numbers is: 12

Michael Fitzgerald - 3 years, 6 months ago

Tally of 10000 random games in Mathimatica ((4,50),(5,513),(6,1320),(7,2017),(8,2437),(9,1770),(10,1275),(11,424),(12,194))

Χωρις Ονομας - 3 years, 6 months ago

this script solves for any sequence of numbers written on the board

Michael Fitzgerald - 3 years, 6 months ago

@Michael Fitzgerald : but the above script doesn't seem to be working for the following numbers- 1,2,3,4,5,6,7. Proceeding in the similar manner, the highest score should have been 6+5+5+4+4+4=28, but i guess, its not happening. Please let me know if I am going wrong anywhere. I am getting 27 here.

puneet sharma - 3 years, 6 months ago

Puneet,
Not sure where you got the third 4
Let's walk through this
1 and 4  erase 4      3
1 and 5  erase 5      4
1 and 6  erase 6      5
1 and 7  erase 1      6
2 and 7  erase 2      5
3 and 7  erase 7      4
                   Total   27

Michael Fitzgerald - 3 years, 6 months ago

At first, I also felt that I can generalize this for n numbers proceeding in the similar manner, but I realized that my argument has no guarantee that this "assumed highest score" is always acheivable. For 7 numbers, this tells us that the highest possible score is certainly less than or equal to 28.

A Former Brilliant Member - 3 years, 6 months ago

For 7 numbers, this tells us that the highest possible score is certainly less than or equal to 28.

Your reasoning is correct, but go a bit further. One of the pairs chosen must include the four, and that means that one of the scores-addends must be 3 or less. Therefore, 6+5+5+4+4+3 =27 is optimal.

Peter Byers - 3 years, 3 months ago

For the instructions given and the first example (2 - 1 = 1, etc.), the latter doesn't match the instructions first given. Those say add yet the sample subtracts. Makes for some uncertainty.

Rhys W Roark - 3 years, 6 months ago

Omar Sayeed Saimum
Nov 6, 2017

STEP 1: Take 1 and 4 . Score 3 . Remove 4

STEP 2: Take 1 and 5 . Score 7 . Remove 1

STEP 3: Take 2 and 5 . Score 10 . Remove 2

STEP 4: Take 3 and 5 . Score 12 . Remove 3

Note that, you can take any arrangement of these steps.

How do you know you cannot do better?

Christopher Boo - 3 years, 7 months ago

The possible positive differences between pairs of numbers are $1,2,3,4$ . After using a pair of numbers, this pair cannot be used again as one of them is discarded.

To maximise the score, we want to maximise the times that we use large differences.To get a difference of 4, we use 1 and 5. To get a difference of 3, we use 1 and 4, or 2 and 5. It is obvious that there must be 4 selections (as that is when the process ends), but it is clear from these deductions above, that the maximum score is using a difference of 4, two lots of a difference of 3, and then the best way is to also use a difference of 2. This gives a total of $4 + 3 + 3 + 2 = 12$ , meaning that this is the maximum, and the solution above shows that it can be done like this.

Stephen Mellor - 3 years, 7 months ago

I'm always cautious when a solution proving maximum/minimum insists that a particular path must be chosen without substantiation. My concern is with "To maximise the score, we want to maximise the times that we use large differences." This is not obvious to me. For example, if the differences were 4, 1, 1, 1, then a difference of 2, 2, 2, 2 would perform better, even though there is fewer "large differences".

Calvin Lin Staff - 3 years, 7 months ago

@Calvin Lin – Your caution is appropriate in most cases. Also, your numerical example also highlights the dangers which could be faced. In this example, it implies that choosing the 4 prevents you from choosing any of the 2s.

However, to attain the upper bound, I have not included the ruling out of any of the cases, despite a number being removed from the whiteboard. If this upper bound is possible (which it clearly is), then it must be the minimum.

Stephen Mellor - 3 years, 7 months ago

@Stephen Mellor – Right, so the better way to present the argument is

Note that every pair of numbers can be used at most once (since we have to delete a number). Hence, the differences must come from the multi-set $\{ 4, 3, 3, 2, 2, 2, 1, 1, 1, 1 \}$ .
Thus, the 4 largest possible differences are 4, 3, 3, 2, which tells us that the best we can do is 14.
The above steps show us that we can get 14.
Hence, 14 is indeed the maximum.

This avoids saying "To maximise the score, we want to maximise the times that we use large differences". But instead, it says "We tabulate the number of times a (large) differences can be attained to determine the theoretically largest score".

Calvin Lin Staff - 3 years, 7 months ago

@Calvin Lin – That is indeed my reasoning. I agree that the language I used could be considered clunky, however.

Stephen Mellor - 3 years, 7 months ago

@Stephen Mellor – It can be tricky to convert what you are thinking down into words, especially in the context of a comment. When you leave out / misphrase an important key point, then it can be hard for others to follow through what you are thinking. That's why I felt it was important to lay out your argument clearly, especially since you I love the argument you had of, "relax the restraints of the problem and consider a slightly more general scenario. Hey, this still applies to our problem!".

Case in point, for the case of 6 numbers, the highest 6 difference are $\{ 5, 4, 4, 3, 3, 3 \}$ , which necessitates the pairs $6-1, 6-2, 5-1, 6-3, 5-2, 4-1$ . Unfortunately, the $6-1-5-2$ cycle means that we cannot restrict to the setup of this problem. Thoughts on how we can extend to larger numbers?

Calvin Lin Staff - 3 years, 7 months ago

It isn't true that you can take any arrangement of these steps. If you started with {1,5} and removed 1, you wouldn't have the 1 available for {1,4}.

Dan Hewitt - 3 years, 6 months ago

We have another possibility. Step1: take 5 and 2 .score 3. remove 2 Step2: take 4 and 1 .score 6 . Remove 4 Step3: take 5 and 1.score 10. Remove any of 1 and 5 Step4:Take the left one with 3 and get score of 12

Shashank Gupta - 3 years, 4 months ago

Do you see how your solution is "equivalent" to his?

Calvin Lin Staff - 3 years, 4 months ago

Amanda Babb
Nov 15, 2017

To maximize your sum, you want to get the highest difference possible from each number before eliminating it.

Option for 1,5: 5 - 1 = 4
Option for 4: 4 - 1 = 3
Option for 2: 5 - 2 = 3
Options for 3: 3 - 1 = 2, 5 - 3 = 2

Note that 2, 3 and 4 occur only once in the set of maximum differences, so those three can each be eliminated without impacting the ability to make the other differences. If they are removed in the first three rounds, the maximum difference of 5-1=4 remains for the final round.

Example:

Round 1: 3 -1 = 2, Eliminate 3, Score 2 (Or 5-3=2), Numbers Remaining: 1,2,4,5
Round 2: 4-1 = 3, Eliminate 4, Score 2+3=5, Numbers Remaining: 1,2,5
Round 3: 5-2=3, Eliminate 2, Score 5+3=8, Numbers Remaining: 1,5
Round 4: 5-1=4, Score: 8+4=12, Eliminated and remaining numbers are irrelevant.

These can be applied in other orders, as long as no number needed for a successive difference is eliminated prematurely. For example, once 2 is eliminated, 5 is only essential for the 5-1=4 difference, so Round 1 could eliminate 2 and Round 2 could then eliminate 5 without impacting the ability to attain those maximum differences.

it really helps you in scool work and other stuff

Gemma Khan - 3 years, 6 months ago

Ariijit Dey
Nov 23, 2017

What are the set of differencs we get? Certainly ${{4,3,2,1}}$ without any constraints. But 4 can occur only once, 3 can occur twice 2 can occur thrice and 1 occurs 4 times. With 3s you can get a sum of atmost 6, with 4 you get a sum of atmost 4 and with 2 a maximum sum of 6 can be found and with 1 it is 3.

Note that I've partitioned the set of sums in the manner with each partition pointing to a fixed difference in the set. THIS WON'T LIKELY LOOSE THE GENERALITY OF THE PROBLEM

Next we can use the Greedy Algorithm . Take the most out of each number. So take two 3's, and you have 6. But now you have to erase 2 numbers out of ${{5,2,4,1}}$ . Erase in such a way that you have the maximum difference left. So erase 2(& not 5) and 4(& not 1). This keeps us with a resullting set of ${{1,5,3}}$ and a sum of 6. Next using the same method choose 1 and 5 to get a difference of 4. Sum is 10. Remove any of the numbers 1 or 5. Next choose 3 and we have a sum of 12.

This Algorithm can be efficiently formulated in a c++ function

Leonel Castillo
Nov 18, 2017

After tinkering around with the game you may end up with the score 12 by first choosing 5-2 = 3 and then erasing 2. Then choosing 4 - 1 = 3 and then erasing 4. Then choosing 5 -1 = 4 and erasing 5. And finally 3-1 = 2 for a grand total of 12. This number looks pretty big compared to your first trials, which in my case yielded 10 so one may try to safely conjecture that 12 is indeed the biggest number that can be obtained. To prove this, let's try to find what someone must have to do in order to get a 13 or higher.

First, it is important to notice that the game has four moves. You would need to obtain 13 points in 4 moves. Let's suppose that you want to obtain 13 points without ever rolling 4 points in a single move. Then an upper bound for your score would be 3 times 4 = 12. This is not enough. Therefore to obtain 13 points you are forced to do a move in which you get 4 points. It is also important to note that if you do a 4-point move, then you can't ever again do a 4-point move given that you will lose either 1 or 5. Now let's try to add up to 13. Suppose your other moves earned you 2 points, 2 points, and 3 points. 2+2+3+4 = 11, not enough. Suppose you made 3+3+2+4 = 12. Not enough (the order of these additions are not meant to indicate the order in which you do the moves. They are just the theoretical total regardless of order.). Therefore you find that to get 13 points you would need to make 3 moves in which you earn 3 points so that 3+3+3+4 = 13. And this allows us to find a contradiction by asking a question: Is it possible to obtain 3 points 3 times? The answer is no. There are only two moves that gain exactly 3 points, (4-1) and (5-2). And after you do them both, there is no other way to get exactly 3 points. Therefore, it is impossible to obtain 13 points and it follows that any amount bigger than 13 is also unreachable.

Agaptios Trikaliotis
Nov 16, 2017

5+4=9-5=4 left 1,2,3,4 2+4=6-4=2 left 1,2,3 3+1=4-3=1 left 1,2 2+1=3-1=2 then 2 and 12 have common number 2 so i am stupid

Victor Hugo Alves Steil
Nov 15, 2017

If you combine the middle numbers (2,3,4) each with their furthest edge number (1 or 5), you will get $3 + 2 + 3 = 8$ , and eliminate just the middle ones (since each of the edge numbers are responsible for more than half of the differences) you will be left with the edge numbers, which have a difference of 4, totaling $\boxed{12}$ .

Alex Wang
Nov 15, 2017

if you pick one, you would erase the smaller one. That makes the score higher. So, do 3,4,and 5, and erase smallest.

Antoine G
Nov 14, 2017

Look at the best partner for a maximum score if one integer is already picked. The maximum score if ...

... 1 is picked is 4.

... 2 is picked is 3.

... 3 is picked is 2.

... 4 is picked is 3.

... 5 is picked is 4.

Since 1 and 5 attain the maximum score together, it can only be used once. So the maximum total score is $4+3+2+3 = 12$ .

Now just achieve this maximum by going through the list (picking 1 and 5 last): choose 2 and 5 removing 2, choose 4 and 1 removing 4, choose 3 and 1 removing 3, choose 1 and 5 removing 5. Since all the maximum have been realised, this is the maximum score.

Whiteboard

9 solutions

0 pending reports