Maths Olympiad Prep

Library / /335 of 520

Combinatorics Difficulty 5.5 AIME, harder Find the answer

Example 2: A rope of length 2009 is operated as follows: first, it is divided into two ropes of positive integer lengths, and the lengths of the two ropes are recorded, then the above operation is repeated on one of the ropes, ... until 2009 ropes of length 1 are obtained. If the lengths of the two ropes obtained in a certain operation are not equal, then this operation is called "good".
(1) Find the maximum and minimum values of the number of good operations;
(2) Prove: In all operation processes where the number of good operations reaches the minimum value, the number of different lengths of ropes recorded is the same.

A number or a short expression. Spacing and $ signs are ignored.

Solution

【Analysis】(1) It is easy to know that a rope of length 2 can only be divided into two segments of length 1, meaning the last operation on the rope must not be a good operation. A rope of length 2009 can be divided into 2009 segments of length 1 after exactly 2008 operations, so the number of good operations is no more than
20081=20072008-1=2007.
Therefore, the maximum number of good operations is 2007.
The following is such an operation: each time, cut a segment of length 1, then the first 2007 operations are all good operations.

Generalize the problem: For a rope of length nn, let f(n)f(n) be the minimum number of good operations.

By conducting mathematical experiments with simple positive integers nn and summarizing the experience, the following two lemmas can be discovered.
Lemma 1: f(n)=0n=2kf(n)=0 \Leftrightarrow n=2^{k}.
Lemma 2: Suppose n=2k1+2k2++2k1(k1>k2n=2^{k_{1}}+2^{k_{2}}+\cdots+2^{k_{1}}\left(k_{1}>k_{2}\right. >>kl0)\left.>\cdots>k_{l} \geqslant 0\right). Let l=S2(n)l=S_{2}(n) \triangleq the sum of the digits of nn in binary. Then f(n)=S2(n)1f(n)=S_{2}(n)-1.

Proof of Lemma 2: Since after l1l-1 good operations, we can obtain 2k1,2k2,,2k12^{k_{1}}, 2^{k_{2}}, \cdots, 2^{k_{1}}, then
f(n)l1f(n) \leqslant l-1.
We will prove by mathematical induction:
f(n)S2(n)1f(n) \geqslant S_{2}(n)-1.
When n=1n=1, it is Lemma 1, and the conclusion is obviously true.
Assume that for nkn \leqslant k, f(n)S2(n)1f(n) \geqslant S_{2}(n)-1.
When n=k+1n=k+1, by the definition of ff, there exists an operation process containing f(k+1)f(k+1) good operations and several non-good operations, which cuts a rope of length k+1k+1 into k+1k+1 segments of length 1. If the first operation in the above process is a good operation, cutting a rope of length k+1k+1 into segments of lengths aa and bb, i.e., k+1=a+b,abk+1=a+b, a \neq b, then
f(k+1)=f(a)+f(b)+1(S2(a)1)+(S2(b)1)+1=S2(a)+S2(b)1S2(a+b)1=S2(k+1)1, \begin{array}{l} f(k+1)=f(a)+f(b)+1 \\ \geqslant\left(S_{2}(a)-1\right)+\left(S_{2}(b)-1\right)+1 \\ =S_{2}(a)+S_{2}(b)-1 \\ \geqslant S_{2}(a+b)-1=S_{2}(k+1)-1, \end{array}

The equality holds if and only if there is no carry in the binary addition of a+ba+b.

If the first operation in the above process is not a good operation, i.e., k+1=2ak+1=2a, then
f(k+1)=2f(a)2(S2(a)1). f(k+1)=2 f(a) \geqslant 2\left(S_{2}(a)-1\right) .

Since S2(2a)S2(a)+S2(a)1S_{2}(2a) \leqslant S_{2}(a)+S_{2}(a)-1, the equality holds if and only if S2(a)=1S_{2}(a)=1, i.e.,
2S2(a)2S2(2a)1. 2 S_{2}(a)-2 \geqslant S_{2}(2a)-1 .

Using this result, we get
f(k+1)2(S2(a)1)S2(2a)1=S2(k+1)1, \begin{array}{l} f(k+1) \geqslant 2\left(S_{2}(a)-1\right) \\ \geqslant S_{2}(2a)-1=S_{2}(k+1)-1, \end{array}

The conclusion holds, and the equality holds if and only if S2(a)=1S_{2}(a)=1.
In summary, Lemma 2 is proved.
Therefore, using the binary representation of 2009, we get
f(2009)=S2(2009)1=7 f(2009)=S_{2}(2009)-1=7 \text {. }
(2) If the binary representation of nn is
n=2k1+2k2++2ki n=2^{k_{1}}+2^{k_{2}}+\cdots+2^{k_{i}} \text {, }

we can set the set M={k1,k2,,kl}M=\left\{k_{1}, k_{2}, \cdots, k_{l}\right\}.
If l2l \geqslant 2, then in any operation process where the number of good operations reaches the minimum, the first operation is a good operation, i.e., there exists a non-empty proper subset LL of MM such that the rope of length nn is cut into segments of lengths aa and bb, where a=kL2k,b=kML2ka=\sum_{k \in L} 2^{k}, b=\sum_{k \in M-L} 2^{k}. Performing l1l-1 good operations in succession produces ll different lengths 2k1,2k2,,2ki2^{k_{1}}, 2^{k_{2}}, \cdots, 2^{k_{i}}.

Then, the non-good operations produce lengths 2k11,2k12,,2,202^{k_{1}-1}, 2^{k_{1}-2}, \cdots, 2,2^{0}, and so on. Therefore, the number of different lengths recorded is l1+k1l-1+k_{1}.

In solving this problem, it is found through mathematical experiments that the minimum number of good operations f(n)f(n) is related to the binary representation of the positive integer nn, and a basic result about the sum of digits is used:
Sp(a+b)=Sp(a)+Sp(b)k(p1), S_{p}(a+b)=S_{p}(a)+S_{p}(b)-k(p-1),

where kk is the number of carries in the addition of a+ba+b in base pp.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.