Given a positive integer $k$ and other two integers $b > w > 1.$ There are two strings of pearls, a string of $b$ black pearls and a string of $w$ white pearls. The length of a string is the number of pearls on it. One cuts these strings in some steps by the following rules. In each step: (i) The strings are ordered by their lengths in a non-increasing order. If there are some strings of equal lengths, then the white ones precede the black ones. Then $k$ first ones (if they consist of more than one pearl) are chosen; if there are less than $k$ strings longer than 1, then one chooses all of them. (ii) Next, one cuts each chosen string into two parts differing in length by at most one. (For instance, if there are strings of $5, 4, 4, 2$ black pearls, strings of $8, 4, 3$ white pearls and $k = 4,$ then the strings of 8 white, 5 black, 4 white and 4 black pearls are cut into the parts $(4,4), (3,2), (2,2)$ and $(2,2)$ respectively.) The process stops immediately after the step when a first isolated white pearl appears. Prove that at this stage, there will still exist a string of at least two black pearls. Proposed by Bill Sands, Thao Do, Canada
Problem
Source: IMO Shortlist 2010, Combinatorics 6
Tags: combinatorics, invariant, game, IMO Shortlist
27.07.2011 12:24
Too interesting problem to be left without solution here! If $S_i$ is a pearl at i-th possition, let by $l(S_i)$ denote the length of $S_i$ and "k-zone" means the strings of pearls that are to be chosen in the next step. Let begin with the simple case k=1. After a few experiments, one can conclude that at each step before the process ends up, at least one of two cases holds: a) Exist white string $S_i^w$ and black string $S_j^b$ at positions $i, j, \,i>j$ , with $l(S_j^b) >l(S_i^w)$. b) Exist white string $S_i^w$ and black string $S_j^b$ at positions $i, j, \,i<j$ , with $l(S_j^b) >\frac{l(S_i^w)}{2}$. Motivated by this simple case, let us proceed with the general one. $Lemma.$ Before each step and prior to the end of the process, at least one of two cases holds: a) Exist white string $S_i^w$ and black string $S_j^b$ at positions $i, j, \,i>j$ , with $l(S_j^b) >l(S_i^w)$. b) Exist white string $S_i^w$ and black string $S_j^b$ at positions $i, j, \,i<j$ , $S_j^b$ is outside k-zone, and $l(S_j^b) > \frac{l(S_i^w)}{2}$. $Proof$: By induction. Before the first step a) holds. Let we are before n+1-th step. Then, by induction assumption, one step back, a) or b) holds. Case 1: After n-th step holds a): $\exists S_i^w, S_j^b,\, i>j,\, l(S_j^b) >l(S_i^w)$. If $S_i^w, S_j^b$ both are in k-zone or outside k-zone, then a) will hold after spawning too. Let now assume that $S_j^b$ is into k-zone and $S_i^w$ is outside. Because we are prior to end of the process, $S_i^w > 1$ and this means that $ j \leq k < i $. If some of strings $S_{j+1}, S{j+2},...,S_k$ is white, then, as said before a) will hold after spawning. Assume all of them are black. If $\frac{l(S_k^b)}{2}>l(S_i^w) $ then a) will hold after next step, if $\frac{l(S_k^b)}{2}\leq l(S_i^w) $ let $S^b$ be the bigger(or one of them, if equal) of 2 strings $S_k^b$ is splitted off. Then $l(S^b) >l(\frac{S_i^w}{2})$. Affter new ordering of strings, $k-1 $ parts, at least one from each splitted string in positions $1,2,...,k-1$, will be before $S^b$; and $S_i^w$ also will be before. Thus, after new ordering, $S^b$ will be outside k-zone and b) will hold with respect to $S_i^w$ and $S^b$. ($S_i^w$ will be at new position of course) Case 2: After n-th step holds b). Then if both $S_i^w, S_j^b$ are outside or inside k-zone, b) will hold also after next step. If $S_i^w$ is in k-zone but $S_j^b$ is outside, then after next step, a) will hold. Now it is easy to be seen that after the end of the process , there will be a string of at least two black pearls.
06.03.2013 02:44
dgrozev wrote: Case 2: After n-th step holds b). Then if both $S_i^w, S_j^b$ are outside or inside k-zone, b) will hold also after next step. If $S_i^w$ is in k-zone but $S_j^b$ is outside, then after next step, a) will hold. I think this has a small hole. But we can fix it by assuming (b) holds but (a) does not, and then taking $i<j$ minimal with $2\le l(S_i^w) \le 2l(S_j^b) - 1 \implies l(S_j^b) \ge 2$. Since $S_j^b$ is outside the $k$-zone by definition, we just distinguish between $i\le k$ and $i>k$. If $i\le k$, then as you've written, $l(S_j^b) > l(S_j^b) -1 \ge \lfloor{l(S_i^w)/2}\rfloor \ge 1$ implies (a) will hold after the next step. Otherwise, if $i>k$, then since we've assumed (a) doesn't hold, $S_1,S_2,\ldots,S_k$ must all be white (or else if $S_u$ is black, $l(S_u)\ge l(S_i^w) \implies l(S_u) > l(S_i^w)$ by the priority of white strings), with $l(S_1^w) \ge \cdots \ge l(S_k^w) \ge 2l(S_j^b)$ by the choice of $i$. But then $S_1^w,\ldots,S_k^w$ will split into $2k$ white strings each at least as long as $S_j^b$, so $S_i^w,S_j^b$ will satisfy (b) again after the next step, by the priority of white strings. --- Also, here's how I would word the case when (a) holds (so $l(S_j^b) > l(S_i^w) \ge 2$), this time with $i-j$ WLOG minimal. If $i-j>1$, then $S_{j+1}$ cannot be black, or else $l(S_{j+1}) \ge l(S_i^w)\implies l(S_{j+1})>l(S_i^w)\ge 2$ (by the priority of white strings), and similarly it cannot be white or else $l(S_j^b) > l(S_{j+1})\ge 2$. Thus $i-j=1$. Of course, if they are both outside the $k$-zone, we clearly get (a) again after a step, while if they're both inside, we use $\lceil{l(S_j^b)/2}\rceil \ge l(S_j^b)/2 > l(S_i^w)/2 \ge \lfloor{l(S_i^w)/2}\rfloor \ge 1$ to get (a) again (unless $l(S_i^w)$ is $2$ or $3$, in which case we're done after the next step). Finally, if $j\le k<i$ (i.e. $j=k$ and $i=k+1$), then we have (a) again if $\lceil{l(S_j^b)/2}\rceil > l(S_i^w)\ge 2$, and (b) if $l(S_i^w) \ge \lceil{l(S_j^b)/2}\rceil \ge 2$, since \[ \lceil{l(S_1)/2}\rceil \ge \cdots \ge \lceil{l(S_{k-1})/2}\rceil \ge \lceil{l(S_k^b)/2}\rceil = \lceil{l(S_j^b)/2}\rceil \] and $l(S_i^w) \le l(S_j^b) - 1 \le 2\lceil{l(S_j^b)/2}\rceil - 1$ (and once we've performed a step, we don't care about the order of length $\lceil{l(S_j^b)/2}\rceil$ black strings). Comment. The key to this approach is that it is very hard to disturb condition (a) in a step (and if we do, we get the extremely restrictive but natural condition (b), which just says the shortest white string cannot be much longer than the longest black string).
10.04.2013 18:01
we assume the opposite so at the end all white. consider the last moment that now all black strings are of length $1$. then some are $2$ some $1$. however in the next step all strings at least $2$ are used and that number is smaller than $k$. let such a configuration have $M$ steps up to this moment now we retrace steps(counting steps from the moment mentioned above) lemma: after the $M-s$-th step all white strings are used in the next step. the length of all white strings is at least $2^{s+1}$,all black strings are of length at most $2^{s+1}$ and there are at most $k$ strings of length at least $2^s+1$. proof by induction Base: $s=0$ was proven above if it is true for some $s<M$ then in the $M-s$-th step if not all white strings were used then all black strings used had length at least $2^{s+1}+1$ and we may pair them with a black string of length at least $2^s+1$(which we got after the division of the black stringwith length at least $2^{s+1}+1$).All other used strings can be paired with a white string. thanks to the pairing we have that the number of used strings is LESS than $k$ and there is a non-used string. That's a contradiction. so all white strings really were used in the $M-s$-th step and then each one of them is of length at least $2^{s+2}$ In addition each string with length $2^{s+1}+1$ can be paired with a string of length at least $2^s+1$(which comes after the $M-s$-th step) since if it was divided than it's clear otherwise there would be a black string of length $2^{s+1}+1$ after the $M-s$-th step. A contradiction. so there are at most $k$ strings of length at least $2^{s+1}+1$ after the $M-(s+1)$-th step. now it's pretty easy to see that each black string after the $M-(s+1)$-th step was of length at most $2^{s+2}$ this completes the induction. so now if $k$ is at least $2$ after the first step it's clear that $w$ is at least $b$. A contradiction if $k=1$ then both black strings must have length less than $2^M+1$(at most $2^M$) and the white one has at least $2^{M+1}$ so again $w$ is at least $b$ A contradiction. This ends the proof.
20.10.2015 06:53
Did I make a mistake somewhere? My proof only requires $w<2b$. Let $b_i,w_i$ be the lengths of longest black and white strings respectively after the $i$-th step. Lemma: $w_i\le 2b_i$. Proof: We prove this by induction.. For $i=0$ it is clearly true. Now suppose it is true for $i-1$. If no black string is cut, then we have $2b_i=2b_{i-1}\ge w_{i-1}\ge w_i$, as desired. If the black string is cut, there are two cases. Either the $w_i$ is one of the strings cut from $w_{i-1}$ or $w_i$ is uncut in $i$-th step. In the second case, we get $2b_i\ge b_{i-1}\ge w_i$ so we are done. In the first case, we know $b_i\ge \lceil \frac{b_{i-1}}{2} \rceil$, so assume that $b_i=\lceil \frac{b_{i-1}}{2} \rceil$. There are $4$ cases: 1. $w_i=2m, b_i=2n$, Then $w_{i-1}=m$ and $b_{i-1}=n$ and $m\le 2n$ so we are done. 2. $w_i=2m+1, b_i=2n$ By the inductive hypothesis, $2m+1\le 4n$, so $m+1\le 2n$ as desired. 3. $w_i=2m, b_i=2n+1$. By the inductive hypothesis $2m\le 4n+2$ so $m\le 2n+1<2n+2$ as desired. 4. $w_i=2m+1, b_i=2n+1$. By the inductive hypothesis $2m+1\le 4n+2$ so $2m+2\le 4n+3$ so $2m+2<4n+4$, hence $m+1<2n+2$ as desired. In any case $w_i\le 2b_i$, so our lemma is proven. Now consider the set of all black strings $B_i$ and the set of all white strings $W_i$ after the $i$-th step. We call the game state "good" if all the white strings are powers of $2$ and $w_i=2b_i$. I claim that the initial game state is good if the problem condition is not satisfied. We prove this by backwards induction. Proof: For the base case consider the point at which $b_k=2$ (this must exist). Then by our lemma, $w_k\le 4$. If there are any white strings of length $3$ or $2$ we are done so all the white strings are of length $4$ as desired. Now for the inductive step, suppose that $W_i=\{2^{a_1},...,2^{a_s}\}$ and $B_i=\{c_1,...,c_t\}$ where $a_1 \ge ...\ge a_s$ and $c_1\ge ... \ge c_t$ and $2^{a_1}=2c_1$. Now since $a_s\ge 1$, it is clear that each element in $W_i$ must have came from a power of $2$, hence $W_{i-1}$ only consists of powers of $2$. Now if $2^{a_1}$ did not come from a string cut in the $i$-th step, then it is easy to see that only white strings of length $2^{a_1}$ were cut in the $i$-th step, so $w_{i-1}=2^{a_1}$ and $b_{i-1}=c_1$ which proves the inductive hypothesis. Otherwise, $2^{a_1}$ came from a string of length $2^{a_1+1}$. Now note that $b_{i-1}\le 2b_i=2^{a_1}$, but by our lemma $b_{i-1}\ge 2^{a_1}$, hence $b_{i-1}=2^{a_1}$ and so in any case the previous game state is good. However this implies that $w=2b$, which is an obvious contradiction. Hence when the first white pearl is isolated there is a black pearl of length at least $2$ as desired.
20.10.2015 21:55
I admit, I didn't read your solution. But apparently there is something... I wouldn't say wrong..., but maybe a different interpretation of the problem. In my opinion the problem should be read as: Each step consists of two sub-steps: (i) and (ii). After a step is completed(which means (ii) is finished completely), we look at the resulting strings of pearls and if there is a isolated white pearl, the process ends up. I think, this is the way the problem was interpreted in the posts above. (at least in my post). Having in mind this interpretation, your claim is false. Consider $k=2$ and the pearls are $(3 w, 2 b)$. Then after the firs step the strings would be $(2w, 1w, 1b, 1b)$. Thus, we have an isolated white pearl, but a string of two (or more) black pearls doesn't exist.
20.10.2015 22:11
Oh I misread the problem and thought that when an isolated white pearl appears we stop cutting strings immediately. Thank you for the clarification.
09.08.2020 03:41
20.03.2023 23:05
Let a $m$-string denote a string of length $m$. Let 'state $i$' denote the configuration of the strings after step $i$ is made. After any number of steps, let 'extras' denote the strings outside the first $k$ (if any). Let $M, M_B, M_W, m, m_b, m_w$ denote the maximum and minimum lengths of strings of any colour, black, and white respectively in a given state. Let the process terminate after step $t$, i.e. the first state where $m_w = 1$. Assume FTSOC that when the process terminates, all black strings are length 1. This means that in state $t$, $M_B = m_b = 1$. Note that a step consists of splitting a $\lambda$-string into $\lfloor \lambda/2 \rfloor$- and $\lceil \lambda/2 \rceil$-strings (including when $\lambda = 1$, in which case we discard the $0$-string). Furthermore, the number of strings is strictly increasing until termination. Let step $p$ denote first step whereby state $p$ contains more than $k$ strings, with $p$ possibly infinite. For all $i \le p$, since state $i-1$ contains $\le k$ strings, all strings are chosen at step $i$. Hence, by induction, in all states $i \le p$ we have $M_B \ge M_W, m_b \ge m_w$. Claim 1: If $t \le p$, contradiction. Proof: In state $t$ all black strings are length 1, hence in state $t-1$ all black strings are length 1 or 2. Yet if in state $t-1$, $m_b = 1$, then $1 \ge m_w \Rightarrow m_w = 1$ contradicts minimality of state $t$. Hence, in state $t-1$, $M_W = m_w = 2$, hence $M_B = m_b = 2$. This implies all strings are length 2, but since all strings were chosen at every step prior, we have the same number of black and white strings, meaning $b = w$ contradiction. $\square$ Henceforth assume $t>p$, $p$ finite. Claim 2: Consider any state $i$. If in state $i-1$, $M \le 2m+2$, then in state $i$ we also have $M \le 2m+2$. Proof: In state $i-1$, let $A, B, C, D$ denote the max of the first $k$, the min of the first $k$, the max of the extras, and the min of the extras respectively. $C, D$ may not exist; in that case ignore them. Note that $A \ge B \ge C \ge D$. We claim that in state $i$, $M = \lceil A/2 \rceil$ or $C$, and $m = \lfloor B/2 \rfloor$ or $D$. Indeed, for max note that $A$ in the first $k$ produces the greatest $\lceil /2 \rceil$ and $C$ in the extras has the greatest value. Analogously, the min is proven. Our 'inductive hypothesis' states that $A \le 2D + 2$, or $A/2 \le D + 1$. We now get: \begin{align*} \lceil A/2 \rceil &\le D + 1 \le 2D + 2\\ C &\le A \le 2D + 2 \\ \lceil A/2 \rceil &\le B + 1 \le 2 \lfloor B/2 \rfloor + 2 \\ C &\le B \le 2 \lfloor B/2 \rfloor + 2. \end{align*}This covers all 4 cases. $\square$ Claim 3: Consider any state $i$. $M_B \le 2m_b + 2$, $M_W \le 2m_w + 2$. Proof: Base case: in state $0$, there is only one string of each colour hence the statement is trivially true. Inductive step: Proceed exactly as above except focus on one colour only (note that $k$ actually has no significance in the proof and need not be constant each step). $\square$ Suppose state $q > 0$ is the first where $M = M_W$. If this is never achieved (in some state $\le t$), then at the state of termination $M_B = M > M_W = 1$ hence contradiction. Thus, $q$ is finite and $q < t$. Claim 4: At state $q$, $M \le 2m+2$. Proof: Assume FTSOC not. Consider state $q-1$ and define $A, B, C, D$ as in the proof of Claim 2. By the converse of Claim 2, $A > 2D + 2$. Hence, by Claim 3, $A, D$ are uniquely strings of opposite colours, as are $M, m$. Yet by minimality of state $j$, $A$ must be black hence $D$ is white. Furthermore, $M$ must be white and $m$ black. $m = \lceil B/2 \rceil$ or $m = D$. Since $D$ is uniquely white and $m$ is uniquely black, $m = \lceil B/2 \rceil$. Hence, we have a black $B$-string in the first $k$. Claim 3 gives $A \le 2B + 2$, so either $M = \lceil A/2 \rceil \le 2 \lfloor B/2 \rfloor + 2$ or $M = C \le 2 \lfloor B/2 \rfloor + 2$. Either way, $M \le 2m + 2$, contradiction. $\square$ Corollary 4.1: In any state $\ge q$, $M \le 2m+2$. Proof: Claims 2 and 4 combined. $\square$ Corollary 4.2: Consider any state where $m = m_b$. Then $M \le 2m+2$. Proof: If $M = M_B$ then Claim 3, if $M = M_W$ then Corollary 4.1. $\square$ Let state $s$ denote the first state with a black 1-string. If $s \le p$, we get $1 = m_b \ge m_w \Rightarrow m_w = 1$, hence $t \le s \le p$ contradiction by Claim 1. Furthermore, if $s = t$ we get in state $s-1$, all strings are length 2. But then all of them must also be chosen in step $s$, so $t \le p$ contradiction by Claim 1. Henceforth assume $s > p, s < t$. Note that since $s > p$, in state $p$ we have $>k$ strings, hence in state $s$ we have $>k + k = 2k$ strings. Equivalently, the extras consist of $>k$ strings. In state $s-1$, we need a black 2- or 3-string (let this be a f-string). By $s < t$, in the first $k$ there cannot exist a white f-string. Hence, the first $k$ must end with a black f-string. Claim 5: Suppose in some state $r$ we have $y > 0$ black f-string and $z > 0$ white f-strings where $y + z > k$. Then contradiction. Proof: Suppose there are $w$ black 2-strings and $x$ white 2-strings. If $x = 0$, then we have $z$ white 3-strings, all of which must be cut before the $y$ black f-strings. However, it's not possible to cut all the black f-strings together with the white 3-strings since $y + z > k$, so after the first of these $z$ white 3-strings is cut there exists a black f-string of length $> 1$. The process has terminated by now, contradiction. Hence assume $x > 0$. Consider the first step which cuts any of the $x$ white 2-strings. Before this, suppose it has cut $u, v$ of the $z-x$ white, $y-w$ black 3-strings respectively. This results in an additional $u$ white 2-strings and $v$ black 2-strings. Note that none of these $(w) + (v)$ black 2-strings could be cut until all the $(u) + (x)$ white 2-strings are cut. Furthermore, in this first step all the remaining $(z-x-u) + (y-w-v)$ 3-strings must be cut. However, it's not possible for all these prescribed strings to be cut in this first step, as $(w + v) + (u + x) + (z - x - u) + (y - w - v) = y + z > k$. Hence, after this first step there exists a black f-string, contradiction. $\square$ We consider cases based on state $s-1$. Note that there must be at least one white string. Case 1: The first $k$ end with some black 2-strings. Then the extras must also end with $>k$ black 2-strings. By Corollary 4.2, $M \le 2m+2$, hence $M \le 6$. If there are white f-strings in the first $k$, in step $s$ they yield 1-strings hence $s = t$ contradiction. Hence, there are only white 4-, 5-, 6-strings. In state $s$, the white strings become f-strings. However, note also that the $>k$ extras black 2-strings are untouched from state $s-1$ to state $s$. By Claim 5, contradiction. Case 2: The first $k$ end with some black 3-strings, but there are white 2-strings in the extras. Since there are $>k$ f-strings in the extras with at least one white f-string, plus at least one black 3-string, contradiction by Claim 5. Case 3: The first $k$ end with some black 3-strings, and there are no white 2-strings in the extras. Hence there are no white strings in the extras, only black f-strings (and $>k$ of them). By Corollary 4.2, $M \le 2m+2$, hence $M \le 8$. Case 3.1: Not all white strings are 8-strings. Hence, there is a white 4-, 5-, 6- or 7-string, and in state $s$, we get a white f-string as well as our $>k$ black f-strings. By Claim 5, contradiction. Case 3.2: All white strings are 8-strings. Suppose there are $\alpha$ white 8-strings, necessarily in the first $k$. Hence there are $k-\alpha$ black $[3, 8]$-strings in the first $k$. Then in state $s$, there are $2\alpha$ white 4-strings, and suppose there are $\beta, \gamma, \delta$ black 2-, 3- and 4-strings respectively as a result of the $k - \alpha$ cut black strings, where $\beta + \gamma + \delta \ge k-\alpha$. This is because each cut black $[3, 8]$-string yields at least one of these. Case 3.2.1: $2\alpha > k$. All the first $k$ strings are white 4-strings. We also maintain the $>k$ black extras f-strings from state $s-1$. Step $s+1$ only cuts white 4-strings into $2k$ white 2-strings, so in state $s+1$ we can apply Claim 5 for a contradiction. Case 3.2.2: $2\alpha \le k$. In step $s+1$, all $2\alpha$ white 4-strings are cut, as well as $k-2\alpha$ black $[2, 4]$-strings, of which there are $>\beta + \gamma + \delta + k > 2k - \alpha$. Note that we obtain $4\alpha > 0$ white 2-strings. If only black 4-strings were cut, then the $>k$ black extras f-strings are maintained so Claim 5 gives a contradiction. If not only black 4-strings were cut, then all black 4-strings were cut, and all uncut black strings yield at least one of either f-strings or 0-strings. Since $>(2k-\alpha) - (k-2\alpha) = k + \alpha > k$ black strings aren't cut, they become f-strings and so Claim 5 gives a contradiction.
29.08.2023 19:19
Allow strings of length $0$, which gets split into two strings length $0$ (which doesn't change anything about the problem, since these are always at the end and never get divided unless everything else is divided too). A string of length $1$ splits into a length $1$ and a length $0$ string. Furthermore, keep track of the number of splits taken to achieve each string at any given point, and within same-colored strings which have the same length, sort the ones that have been cut less often towards the left (this changes nothing but will make proving a claim easier). A string of length $n$ splits into strings of lengths $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$. It is then not difficult to see by induction that the possible lengths of a string of black pearls obtained by cutting the original $a$ times is either $\lfloor b/2^a\rfloor$ and $\lceil b/2^a\rceil$, and that if we cut every string exactly $a$ times then both of these will occur, and the same is true for the white pearls. In particular, if we cut every string the same number of times, the (unweighted) average length of a black string must be at least the (unweighted) average length of a white string, and equality cannot occur if all of the black strings or all of the white strings are the same length. Call this the size estimate; when we invoke it, the phrase "average length" refers to the unweighted average. Furthermore, if there exists a black string $s_1$ that has been split exactly $a$ times for some $a \geq 0$, there cannot also exist a black string $s_2$ that has been split at least $a+2$ times. Indeed, suppose that this occurs and take the earliest position where this occurs. Then $s_2$ must have just been split, and $s_1$ cannot have just been split, but this means that in the previous position $s_2$ was to the right of $s_1$, since $n \geq \lceil n/2\rceil$, so $s_1$ must have been split along with $s_2$: contradiction. Now suppose that when the process stops, every string of black pearls has length $1$. Consider the last position in which there exist black pearls of length at least $2$, and call this position 1. Then all of the white strings have length at least $2$, and none of the black strings have length at least $3$, hence every white string is to the right of every black string. This means that all of the white strings, as well as every black string of length $2$ (of which there are at least $1$), are within the leftmost $k$ strings—in particular, there are at most $k-1$ white strings at this moment. Now consider the position when we first have more than $k$ strings total, and call this position 2. If the process ends at or before this moment, then in the final position there are necessarily white strings of length $1$ and possibly of length $2$, but nothing else, and there are only black strings of lengths $1$ and $0$. But this contradicts the size estimate. Furthermore, there must exist some black string of length at least $3$, since otherwise the average length of the black strings is at most the average length of the white dreams, with equality only occurring if every string is length $2$, again contradicting the size estimate. This means that this position must occur before position 1. Finally, note that there are more than $k/2$ black (equiv. white) strings present in position 2, but at most $k$. Furthermore, there cannot exist exactly $k$ white strings, since otherwise in position 1 least $k$ white strings, so the number of black (equiv. white) strings is in the interval $(k/2,k)$. Consider every white string present in position 2. Between position 2 and position 1 (inclusive) some white string cannot have been split, since otherwise we would end up with more than $k$ white strings in position 2. I claim that this implies the existence of some white string in position 1 which has length $2$ (note that no white strings have length $1$). Suppose that every white string has length at least $3$. To go from position 1 (which we proved has a black string of length at least $3$) to position 2, we can have to split every black string of length either $3$ or $4$ that shows up at some point. If any black string of length $3$ ever appears (and thus gets split), then every previously unsplit white string must have gotten split with it, since they are all to its right, so only black strings of length $4$ appear. This also means that black strings of length $5$ never appear, since when these are split they produce strings of length $3$ (in particular, this would imply that $b$ is a power of $2$). In position 1, we must have at least one black string of length $1$, since otherwise we need to cut every white string and every black string present in position $1$, but already in position $2$ we have too many strings to do this. On the other hand, if we suppose that the situation in the above paragraph holds, then the only way to obtain a black string of length $1$ is by cutting a black string of length $2$ at some point, but this would also cut every previously uncut white string, all of which have length at least $3$. This proves that some white string of length $2$ exists in position 1, so every white string has length at most $3$ in position 1. Since there are less than $k$ black strings, some white string must get cut immediately after position 1, thus producing a white string of length $1$ and stopping the process. However, since there is also some black string of length at least $3$ present before the cut, there must be some black string of length at least $2$ present after the cut: contradiction. $\blacksquare$ Remark: Thinking about position 1 is important and natural but frustratingly you don't have much information about the white strings, which feels like it's important. On the other hand it intuitively doesn't feel like our string lengths can be that far apart, and considering the number of splits gives us somewhat of a handle on this (actually I did this first and then totally forgot about it wasting about half an hour until I remembered oops), although relating opposite-color splits is still somewhat tricky (you can do this inductively, and I thought about it, but finding the correct claims is hard and not super natural imo). Up to this point, we actually don't use the fact that $k$ is fixed at all, only that we take some leftmost strings and cut all of them, but we have to incorporate this condition into a solution somehow (unless the problem is really stupid). Looking at position 1 again we have a strong condition that $k$ should be pretty big, since it should contain all of the white strings, but on the other hand if $k$ is large then the first several operations just cut every string until $k$ is no longer very large relative to the number of white strings, motivating the introduction of position 2. The observation that some white string in position 2 is not cut between position 2 and position 1 is also important and natural, and this is enough to motivate the final claim and finish the problem. However, there are a number of annoying edge cases, such as proving that position 1 isn't "degenerate" and also occurs before position 2.
08.02.2024 20:43
Here is what I consider to be a horrible solution. Throughout the solution, whenever we say "move" we are referring to the given process of splitting strings. Call a string black if it consists of black pearls and call it white otherwise. Let $B$ and $W$ be the sets of black and white strings respectively. For all strings $T$, we denote by $f(T)$ the length of $T$. Finally, assume for contradiction that there exists a pair of positive integers $b > w$ that doesn't satisfy the given condition. Claim 1: No matter how many times we apply the given process, we have $2\min(f(S) \mid S \in B)+2 \geq \max(f(S) \mid S \in B \cup W)$. Assume the contrary and consider the first instance where our claim fails to be true. Then the length of the smallest black string must have decreased in the previous move, since the length of the longest string cannot increase. Therefore, there exists a black string $T$ that we split in the previous move to create the current shortest black string. It is clear that this string has length at least $\frac{f(T)-1}{2}$. Let $A$ be the longest string split in the previous move and let $B$ be the longest string that was not split in the previous move. By assumption, we have $2f(T)+2 \geq f(A)$ and $f(T) \geq f(B)$. It is clear that the current longest string is either $B$ or a string resulting from splitting $A$ in half. If $B$ is the current longest string, we get $2 \cdot \frac{f(T)-1}{2}+2 = f(T)+1 > f(B)$ a contradiction. Otherwise, we have $\frac{f(A)+1}{2} > f(T)+1 \geq \frac{f(A)}{2}$ which implies that $f(T)+1=\frac{f(A)}{2}$. Then the current longest string must have length $f(T)+1$ since $f(A)$ is even, a contradiction. $\square$ Claim 2: $w < 4k$. Consider the first instance where there is an isolated black pearl among the strings. By Claim 1, each string has at most $4$ pearls. If at this point each black string has only one pearl, we must have split all black strings (which should have two pearls each) in the previous move. Combined with the fact that during each move we split at most $k$ strings, this implies that $2k \geq b > w$. Otherwise, we continue the given process until all black strings have turned into isolated pearls. Observe that in the previous move, we must have split every single string that contains more than $1$ pearl. In particular, we should have split every white string. Combined with the fact that each string has at most $4$ pearls, this implies that $w < 4k$. $\square$ Claim 3: $w$ cannot be a power of $2$. Assume the contrary and let $w = 2^ \alpha$. We begin by proving that $w < 2k$. Suppose that this is not the case. Then $b > 2k$. Observe that by Claim 2, during the first $\alpha-2$ moves of our "algorithm" we split every string in half. Hence, after the first $\alpha-2$ moves each white string will have exactly $4$ pearls. It is clear that at this point there are no isolated black pearls among the strings. Therefore, consider the first instance where an isolated black pearl appears. In the preceding move, we must have split a black string with at most $3$ pearls so, we must have split all of the white strings. Hence, currently each white string must contain exactly $2$ pearls. Since $w \geq 2k$ there are currently at least $k$ white strings with $2$ pearls. Paired with the fact that we split at most $k$ strings per move, this implies that we must split at least one white string before we split a black string with $2$ pearls, a contradiction. Now, during the first $\alpha-1$ moves of our algorithm we split every string in half. Hence, after the first $\alpha-1$ moves, each white string contains exactly $2$ pearls. Since $w < 2k$ there are currently less than $k$ black strings which implies that we will split at least one white string during the next move creating an isolated white pearl, a contradiction. $\square$ Let $d = \lfloor \log_2 k \rfloor$. Similarly as in Claim 3, during the first $d$ moves of our algorithm we split every string in half. Observe that by a simple induction, the absolute difference between the length of the longest white string and the shortest white string will be at most one as long as we split every string during each move. Hence, the length of the current longest white string is greater than $4$ and no greater than $8$. Suppose that it is $8$. Since $w$ cannot be a power of $2$ there must be a white string with $7$ pearls. Consider the first instance where the smallest black string has length at most $3$. It is clear that currently, there are no isolated black pearls among the strings. In the previous move, we must have split a black string of length no more than $7$ to create the current shortest black string. Hence, we split each white string with length no less than $7$. This implies that there is currently a white string with $3$ pearls (Since we split the white string with $7$ pearls). Now, consider the first instance where an isolated black pearl appears. We have established that $b > w > 2k$ in Claim 3 so, there is a black string containing more than $1$ pearl. In the previous move, we must have split every white string containing at least $3$ pearls which in turn creates an isolated white pearl, a contradiction. Now, suppose that it is not $8$. Then, during the next move a white string with $3$ pearls must appear. Then, we are done using the same argument as in the other case. $\blacksquare$
16.02.2025 09:22
This is so horrific its probably wrong, and it just amounts to consider what happens for small values of the maximum bead size . Discussed with math_combo01 but this solution is my atrocity alone. Let $M_i, m_i$ be the largest and smallest beads of color $i$ for $i \in \{w, b\}$. Claim: For both $i$, we have that $M_i \le 2m_i + 1$. Proof: All the beads of the color $i$ lie in an interval $[n, 2n+2]$ for some $n$ inductively. $\blacksquare$ Claim: We have that $M_w \le 2 \cdot m_b, M_w < 2 \cdot M_b$. Proof: This follows inductively. $\blacksquare$ Call a configuration dominating if $M_w > M_b$ and $dire$ if M_b \ge M_w. Call the first $k$ strings in the order the window. Claim: a dominating configuration can't become a state with all black strings of length $1$. Proof: If $M_w = 2$ then $M_b = 1$ so we win already, else $M_w \ge 3$. Call a dire situation in which there exists a black string of length $\ge 2$ not in the window secure. Call the largest such string the security element. Call a situation in which the window contains a white string of length $\ge 3$ not as the first string a silly situation. Claim: All silly configurations become secure or dominating again after applying enough operations. Proof: We repeatedly cut while we aren't secure or dominating. This means that we iteratively have a first black string in the window which isn't the first one. At some point, this string must have length $3$ or $4$. If any black element has length less than $4$ then applying the cutting operation wins. This means that all the elements after it in the window must also be black strings and all elements before it have length at least $4$. If all the black strings after this in the window have length at least $3$ then applying the cutting operation gives us a secure string or a dominating string. Else, a black string in the window has length at most $2$, so by precedence all the white strings have lengths that aren't $2$. Since $M_w \le 2 \cdot m_b$ this means that all white strings have length $4$ and all black strings have lengths that are either $2$ or $3$. Due to being insecure it must follow that there are exactly $k$ strings at this point, since there can't be black strings of length $1$. This means that every string has been repeatedly cut this point, however this contradicts $b > w$ at this point. $\blacksquare$ Claim: All dominating configurations become secure or dominating again after applying enough operations. Proof: For a dominating configuration with $M_w = 2$, we win instantly. If $M_w \in \{3, 4\}$ and the window contains an white string, we win. If the window contains a black string of length $2$ then it must contain a white string of length $1$ so we win as before. Else, the window contains all black strings of length at least $3$, and all white strings have length $2$. Then applying the cutting operation gives $k$ black strings of length $2$, of which one doesn't lie in the window because of the white string of length $2$ getting precedence. Else, suppose the configuration is dominating with $M_w \ge 5$, then cutting gives a silly configuration, a secure one, or a dominating one $\blacksquare$. Claim: A secure configuration becomes another secure or dominating state or we win. Proof: If our security element is at least $3$ or $M_w \le 3$, then after one operation we are either secure or silly once again. Else, suppose our security element is $2$. If the configuration is silly we finish as before, else this means that all black strings have length $2$ or $1$. If a black string has length $1$ then $M_w = 2$ so applying one operation finishes. Else, all black strings have length $2$, so all white string have length $4$ or $3$ or $2$. If any white string of length $3$ or $2$ is in the window we win after one operation, else all white strings in the window have length $4$, so the window becomes all white strings of length $3$ or $2$ after one operation and we win after another. $\blacksquare$ This finishes.