# How find the what is the minimum number of operations required that the sums of any number of numbers in the list can never be $2014$

Question:

Initially we have a list of numbers $1,2,3,\cdots,2013$.an operation is defined that taking two numbers $a, b$ out from the list, but add $a+b$ into it instead, what is the minimum number of operations required that the sums of any number of numbers in the list can never be $2014$

This is Math competition in jiangxi province in 2014 the first problem

my idea: if we change this digital: such this:

Initially we have a list of numbers $1,2,3,4,5$.an operation is defined that taking two numbers $a,b$ out from the list, but add $a+b$ into it instead, what is the minimum number of operations required that the sums of any number of numbers in the list can never be $6$

if we an operation is defined that taking two numbers $1,2$then add $1+2=3$,so must operation is defined that taking two numbers $3,3$ out from the list.and $3+3$.so we at lest operation two.

It is said this reslut is $1007$ Thank you for you help

The minimum number of operations is either $503$ or $504$. I cannot figure out which is the answer.

Among the list of $2013$ numbers $( 1, 2, \ldots, 2013 )$, there are $1006$ pairs that sum to $2014$: $$( 1, 2013), ( 2, 2012 ), \ldots, ( 1006, 1008 )\tag{*1}$$

In order for the final list and the sum of elements in the list doesn't contain $2014$, we must break all these pairs. Since each operation can break at most $2$ pairs, we need at least $503 = 1006/2$ operations to break all these pairs.

On the other hand, the original list contains $504$ pairs that sum to $1009$.

$$( 1, 1008 ), ( 2, 1007 ), \ldots, (7,1002),\ldots, ( 504, 505 )\tag{*2}$$

We can use $504$ operations to transform the list to one with $505$ copies of $1009$ together with extra $1004$ numbers greater than $1009$.

$$(\;\underbrace{1009, 1009, \ldots, 1009}_{505\text{ copies}}, 1010, 1011, \ldots, 2013\;)$$

Individually, each elements of this list are smaller than $2014$ and yet the sum of any two of them is at least $2018$. This implies at most $504$ operations is enough to meet the requirement.

• ,Hello,It is said this answer is $1007$,and I don't sure that $1007$ is answer.Thank you for you help – math110 Apr 12 '14 at 8:51
• @math110 May be you can give us a link of the original problem in Chinese. It is possible something is missing during translation of the problem to English. – achille hui Apr 12 '14 at 8:58
• Oh,and you know chinese? It's nice.I Upload it.Thank you – math110 Apr 12 '14 at 9:01
• or can trangslation:starting by writing integers 1,2,3....2013,at each step,we erase number a,b, and write down a+b. what is the minimum number of steps it takes such that no sums of arbitrary number of remaining integers equal 2014. – math110 Apr 12 '14 at 9:03
• @math110, the translation to English is correct. I cannot see how can the minimum number of operations is $1007$. – achille hui Apr 12 '14 at 9:06

EDIT:

I originally had the interpretation that after taking two pieces of paper with numbers written on them, we add the two together and put a piece of paper with that new number on it into the bag. This allows for duplicates (e.g. two copies of "$3$"). The following solution is for the situation where duplicates are not allowed:

Leave $a=1$ and $b=2013$ unoperated on and perform the following operations:

Step $1$ -> take $2012$ and $2011$ and add them together to get $s_1 = 4023$ Step $n$ -> take $s_{n-1}$ and $2012-n$, add them to get $s_n = s_{n-1}+2012-n$

This can be done for $n=1,\ldots,2011$, at which point the remaining elements of the set are $1,2013$, and $t_{2011} = \sum_{i=2}^{2012} i$. It is necessary to perform one more operation at this point, so the number is at least $2012$.

On the other hand suppose that $2012$ operations have been performed. At this point at most $2$ numbers can remain in the set (every operation reduces the number of elements by at least $1$), but it isn't possible that both are less than $2014$, so the number is exactly $2012$.

• Jesus, mon you figured dat chit out? I didn't even make it through the question post, lolz. I'm soo stained now, bra. – Shine On You Crazy Diamond Apr 12 '14 at 6:18
• It is said this reslut is $1007$ – math110 Apr 12 '14 at 8:47
• @math110 I think I must not be understanding something about the question if the answer is truly $1007$, because as you can see I've given an example of series of operations with $2011$ steps which still leave the possibility of producing $2014$ with one more operation. Could you clarify if anything in my solution indicates a misinterpretation? Xiexie! – user139388 Apr 12 '14 at 17:37