1
$\begingroup$

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.

enter image description here It is said this reslut is $1007$ Thank you for you help

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ,Hello,It is said this answer is $1007$,and I don't sure that $1007$ is answer.Thank you for you help $\endgroup$ – math110 Apr 12 '14 at 8:51
  • $\begingroup$ @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. $\endgroup$ – achille hui Apr 12 '14 at 8:58
  • $\begingroup$ Oh,and you know chinese? It's nice.I Upload it.Thank you $\endgroup$ – math110 Apr 12 '14 at 9:01
  • $\begingroup$ 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. $\endgroup$ – math110 Apr 12 '14 at 9:03
  • $\begingroup$ @math110, the translation to English is correct. I cannot see how can the minimum number of operations is $1007$. $\endgroup$ – achille hui Apr 12 '14 at 9:06
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Jesus, mon you figured dat chit out? I didn't even make it through the question post, lolz. I'm soo stained now, bra. $\endgroup$ – Shine On You Crazy Diamond Apr 12 '14 at 6:18
  • $\begingroup$ It is said this reslut is $1007$ $\endgroup$ – math110 Apr 12 '14 at 8:47
  • $\begingroup$ @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! $\endgroup$ – user139388 Apr 12 '14 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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