In a bag there are $1007$ black and $1007$ white balls, which are randomly numbered $1$ to $2014$. In every step we draw one ball and put it on the table; also if we want to, we may choose two different colored balls from the table and put them in a different bag. If we do that we earn points equal to the absolute value of their differences. How many points can we guarantee to earn after $2014$ steps?
Problem
Source: Turkey NO-2014 Day 1 Problem 1
Tags: absolute value, combinatorics proposed, combinatorics
17.11.2014 20:57
It seems trivial, so maybe I missed something, but we can always guarante $1007\cdot 1007$ points. Divide black balls into two groups, one where all are bigger than $1007$ and one where all are less or equal than $1007$; do the same with white balls. Now, just pair balls bigger than $1007$ with balls that are less or equal than $1007$ and of a different colour. Do the same with balls that are left, so we are done.
17.11.2014 21:11
We are using the numbers for the all balls, I mean not for every group
17.11.2014 21:32
Yes,I used that in my solution,there is a typo,black balls instead of black points.
17.11.2014 21:36
But in every numbering type you have to guarantee the number
17.11.2014 21:39
Yes and I guarantee $1007*1007$ and I explained it in my solution.
17.11.2014 21:49
I don't think the question is wrongly translated but if it is please let me know
19.11.2014 06:56
Your solution is correct if we can do all the scoring moves at the end. As I read the problem though, you can only do one scoring move after every ball taken, so you cannot just delay everything to the end, you must also score in the middle.
19.11.2014 08:39
Nivynum wrote: In every step we draw one ball and put it on the table; also if we want to, we may choose two different colored balls from the table and put them in a different bag. That does not seem the case - see the quoted part, it says if we want to; also, after the first move, no scoring move can be done.
20.11.2014 13:23
Answer : $1007^2$ hint: prove , if player waits 1007 step , he can find in every step two different balls such that one belongs to ${1,...,1007}$ and one belongs to ${1008,...,2014}$ . In order to prove this say we cant find such pair of balls in $(1007+n).$ step and rest is trivial by contradiction.
01.12.2021 14:25
Here is my solution: We are going to show that if there are $2k$ balls in the beginning, the answer is $k^2$. Let's denote $T_p$ with sums of the points we earn after 2014 steps. Every point that we can earn is equal to sum of two positive integer between $0$ and $2k+1$. So it is easy to show that $T_p \leq ((2k)+(2k-1)+(2k-2)+...+(k+1))-((k)+(k-1)+(k-2)+...+3+2+1) \implies T_p \leq k^2$. Claim: If there are $2k$ balls in the bag at the beginning, for all possible dyeings, including $A: (2k,2k-1,2k-2,...,k+1) $ and $B: (k,k-1,...,2,1) $ there exist a one-to-one function that maps the elements of $A$ with the elements of $B$ such that for every two paired elements, one is painted white and the other is painted black. Proof: We are going to prove it by using induction. For $k=1$, $A:(2) $ and $B: (1) $ $\implies$ $(1,2)$ provides the desired match. Suppose the claim is true for $k=m$. For $k=m+1$ we will only review for $2m+2$. WLOG say $2m+2$ is painted black.There are two cases: $1)$ If $m+1$ is painted white we can match $2m+2$ with $m+1$ and remaining mapping is equivalent to $k=m$. $2)$ If $m+1$ is painted black, that means if we do the matching for $k=m$ to the other elements of $A$ and $B$ there gonna exist such a pair $(a,b)$ ( $a \in A$ and $b \in B$ ) a and b will be painted with same colour. Otherwise the number of balls painted in one of the colors would be more than $m+1$. We can't match $(a,b)$ anymore but we can match $(2m+2,b) and (a,m+1)$ now. And the other matches will still provide the desired match. We are done. All we have to show is that there exist moves to make these matches. I left that part to reader because it's not advanced thinking required.