Initially the equation ⋆1x−1⋆1x−2⋆1x−4...⋆1x−22023=0 is written on the board. In each turn Aslı and Zehra deletes one of the stars in the equation and writes + or − instead. The first move is performed by Aslı and continues in order. What is the maximum number of real solutions Aslı can guarantee after all the stars have been replaced by signs?
Problem
Source: 2023 Turkey TST D3 P8
Tags: algebra
05.04.2023 22:24
Observations. Let f(x)=2023∑i=0si1x−2ibe the resulting function, where si∈{−1,1} f(x) has a polynomial in its numerator and degree of this polynomial is 2022 if ∑si=0, and 2023 otherwise. Note that f(x) is continuous on the intervals (2i,2i+1) and lim and \lim_{\epsilon\rightarrow 0^+}f(2^i-\epsilon)=-s_i\infty. Therefore, if s_is_{i+1}=1, i.e. consecutive same signs, then f(x) has a root between x=2^i and x=2^{i+1} because f(2^i+\epsilon) and f(2^{i+1}-\epsilon) have the opposite signs. There are 2023 consecutive sign pairs. Claim. A can guarantee at least 1011 consecutive same sign pairs. (Hence, at least 1011 real root) Proof. A divides 2024 stars into 1011 disjoint consecutive pairs and starts by changing one of the two remaining stars which are not part of a disjoint pair to a sign. A then changes the other star in whichever disjoint pair B touches, to the same as what B did. Claim. B can allow at most 1011 consecutive same sign pairs. (Equivalently, B can guarantee at least 1012 consecutive opposite sign pairs.) Proof. B divides 2024 stars into 1012 disjoint consecutive pairs and changes the other star in whichever disjoint pair A touches, to the opposite of what A did. However, the strategy for B described above makes \sum s_i=0, which implies that f(x) has an even degree polynomial in its numerator, hence it must have an even number of real roots. We need to slightly change the strategy. In the last step, B puts the opposite sign instead of the same, to make \sum s_i\not=0. By doing this, B allows at most 1012 consecutive same sign pairs instead of 1011 but this time f(x) has an odd number of real roots. So, B effectively allows at most 1011 real roots. Answer. 1011
24.04.2023 19:02
B has another way to guarantee both \sum s_i\not=0 and only 1011 consecutive same sign pairs . In the 1st step, if A change the xth star, B just need to change the(x+3)th or (x+3)th star into the same sign. and in all of the other steps, B should change a star into the opposite sign of A does justly. Speacialy, if A changes one of the two star between the firtst two, B change the other one into the opposite sign. AnSoLiN wrote: Observations. Let f(x)=\sum_{i=0}^{2023}s_i \frac{1}{x-2^i}be the resulting function, where s_i\in\{-1,1\} f(x) has a polynomial in its numerator and degree of this polynomial is 2022 if \sum s_i=0, and 2023 otherwise. Note that f(x) is continuous on the intervals (2^i,2^{i+1}) and \lim_{\epsilon\rightarrow 0^+}f(2^i+\epsilon)=s_i\infty and \lim_{\epsilon\rightarrow 0^+}f(2^i-\epsilon)=-s_i\infty. Therefore, if s_is_{i+1}=1, i.e. consecutive same signs, then f(x) has a root between x=2^i and x=2^{i+1} because f(2^i+\epsilon) and f(2^{i+1}-\epsilon) have the opposite signs. There are 2023 consecutive sign pairs. Claim. A can guarantee at least 1011 consecutive same sign pairs. (Hence, at least 1011 real root) Proof. A divides 2024 stars into 1011 disjoint consecutive pairs and starts by changing one of the two remaining stars which are not part of a disjoint pair to a sign. A then changes the other star in whichever disjoint pair B touches, to the same as what B did. Claim. B can allow at most 1011 consecutive same sign pairs. (Equivalently, B can guarantee at least 1012 consecutive opposite sign pairs.) Proof. B divides 2024 stars into 1012 disjoint consecutive pairs and changes the other star in whichever disjoint pair A touches, to the opposite of what A did. However, the strategy for B described above makes \sum s_i=0, which implies that f(x) has an even degree polynomial in its numerator, hence it must have an even number of real roots. We need to slightly change the strategy. In the last step, B puts the opposite sign instead of the same, to make \sum s_i\not=0. By doing this, B allows at most 1012 consecutive same sign pairs instead of 1011 but this time f(x) has an odd number of real roots. So, B effectively allows at most 1011 real roots. Answer. 1011
25.04.2023 01:45
Showing that B can guarantee at most 1011 consecutive same sign pairs does not suffice to show that there will be at most 1011 real roots of the resulting function, you have to show that there can be at most one root in each interval, and that there can be no roots in the interval where the signs of the function are the same at endpoints. I've heard that pairing up (0,2023),(1,2),(2,3),\dots, (2021,2022) and putting the opposite sign in each turn works but proving this seems nontrivial, so bumping for a complete solution.