A finite sequence of integers $a_1, a_2, \dots, a_n$ is called regular if there exists a real number $x$ satisfying \[ \left\lfloor kx \right\rfloor = a_k \quad \text{for } 1 \le k \le n. \] Given a regular sequence $a_1, a_2, \dots, a_n$, for $1 \le k \le n$ we say that the term $a_k$ is forced if the following condition is satisfied: the sequence \[ a_1, a_2, \dots, a_{k-1}, b \] is regular if and only if $b = a_k$. Find the maximum possible number of forced terms in a regular sequence with $1000$ terms.
Problem
Source: USA TSTST 2013, Problem 2
Tags: floor function, inequalities, function, logarithms, algebra
hyperbolictangent
18.10.2013 01:04
I really liked this problem - I think it ties together several nice ideas, one of which is particularly familiar. However, the solution was not obvious (at least not for me), so I'd like to include some heuristics that motivate it and prove to be surprisingly close to optimal. To start with, it's clear that knowing $a_i$ allows us to situate $x$ between two consecutive fractions of denominator $i$; that is, we can find $n_i$ with \[\frac{n_i}{i} \le a_i < \frac{n_i + 1}{i} \; \; \; \; (1)\] Then knowing $a_1, a_2, \dots, a_i$ give us $i$ such inequalities; taking the greatest lower bound and the least upper bound among them allow us to locate $x$ in some half-open interval which we'll call $I_i$. Notice that all possible values for $x$ are contained in this interval, and that every number in this interval is consistent with the known information. It's also easy to see from $(1)$ that $a_{i + 1}$ is forced if and only if there are no fractions with denominator $i + 1$ in $I_i$. (In fact, if there is a fraction with denominator $i + 1$ in $I_i$ there is at most one of them; this follows from the fact that $I_i$ has length at most $1/i$ - consider the constituent inequalities - and that two fractions of denominator $i + 1$ would force \[|I_i| \ge \frac{1}{i(i + 1)} + \frac{1}{i + 1} + \frac{1}{i(i + 1)} > \frac{1}{i}\] since the endpoints of $I_i$ have denominators at most $i$, contradiction.) At this point, we might opt for a hands-off approach. Suppose $a_{i + 1}$ is not forced; then there exists $n_{i + 1}$ with either \[f(n) = \begin{cases} x \in I_i \cap (-\infty, \frac{n_{i + 1}}{i + 1}) \\ x \in I_i \cap [\frac{n_{i + 1}}{i + 1}, \infty) \end{cases}\] Since these two intervals partition $I_i$, one of them has length at most $|I_i|/2$. Therefore by careful choice of $a_{i + 1}$, we can guarantee $|I_{i + 1}| \le |I_i|/2$. In other words, for each $i$ either $a_i$ is forced or $I_{i}$ halves in size. Clearly $a_1$ is unforced, and $|I_1| = 1$ always; then if at least $20$ other $a_i$ are unforced, we will have an interval of size at most $(1/2)^{20}$. Now, at most one other $a_i$ can be unforced, since two fractions of denominator at most $1/1000$ can differ by at least $(1/1000)^2 > (1/2)^{20}$ so they cannot both live in an interval of length at most $(1/2)^{20}$. In all, this proves we can have at least $1000 - 22 = 978$ forced terms. However, if we care to get our hands dirty we can surely do better than halve the interval; this loss of strength will likely be reflected in the answer. Trying some small cases, we see, for instance, that we might want to choose say $a_1 = 0$, $a_2 = 1$, $a_3 = 1$ in order to place $x$ in $[1/2, 2/3)$, which has size $1/6 < 1/4$. Happily, this forces $a_4 = 2$ so that $a_5$ is the next unforced $a_i$, since $3/5 \in [1/2, 2/3)$. Looking back, from $a_1$ we could say $0/1 \le x < 1/1$, after which we found the fraction $1/2 = (0 + 1)/(1 + 1)$ in $I_1$ which unforced $a_2$; then $(1 + 1)/(2 + 1) = 2/3$ in $I_2$ meant $a_3$ was unforced. We are tracing a path down the Stern-Brocot tree - this is not coincidental. Suppose we have $I_j = [a/b, c/d)$. In order to force as many future terms as possible, we want as few fractions with small denominators in $I_j$ as possible. Unfortunately, the fraction $(a + c)/(b + d)$ is always in $I_j$, so this is the best we can possibly do. Fortunately, if $a/b$ and $c/d$ are neighboring elements in some row of the Stern-Brocot tree, we can state with conviction that no fractions of smaller denominator than $b + d$ can be found in $I_j$. This follows from the fact that the Stern-Brocot tree generates all rational numbers, and that entries in the tree never have to be reduced; since the very next mediant inserted between $a/b$ and $c/d$ is $(a + c)/(b + d)$ has denominator $b + d$, all subsequent mediants (i.e. rational numbers in $I_j$) must have denominator strictly bigger. We're now prepared to answer the original question. Since $a_1$ is always unforced, for simplicity assume $a_1 = 0$ so that $I_1 = [0, 1)$; we lose no generality since shifting $x$ by an integer affects the floor function predictably. By our earlier observation, we want to greedily choose intervals to maximize the sum-of-denominators of the endpoints. The next unforced $a_i$ is $a_2$; we can choose either of $[0, 1/2)$ or $[1/2, 1)$ since both have the same denominator sum. Let's use the latter; the next unforced $a_i$ is $a_{2 + 1} = a_3$, and we must pick between $[1/2, 2/3)$ and $[2/3, 1)$. We choose the former, so that the next unforced $a_i$ is $a_{2 + 3} = a_5$. The two possible intervals are now $[1/2, 3/5)$ and $[3/5, 2/3)$; we'll choose the second one, so that the next unforced $a_i$ is $a_{5 + 3} = a_8$. It's fairly clear that the $a_i$ that are unforced are exactly the $a_i$ where $i = F_j, j \ge 2$ is a Fibonacci number; since $F_{16} < 1000 < F_{17}$, there are exactly $16 - 2 + 1 = 15$ unforced $a_i$, leaving the maximum possible number of $1000 - 15 = 985$ forced $a_i$. Remark 1: Notice this is only very slightly better than the heuristic; the heuristic gives roughly $\log_{\sqrt{2}}{n}$ unforced $a_i$ while the tight bound gives roughly $\log_{\phi}{n}$ unforced $a_i$. The difference is not pronounced for small $n$. Remark 2: I did not furnish a proof of the results regarding the Stern-Brocot tree, since they're fairly well known. If you're interested, though, I encourage you to read this; proofs of the classical results can be found at the beginning, while the body of the paper treats the issue of reduced mediants.
v_Enhance
04.09.2015 00:59
It is pretty nice, though I found it not difficult especially in comparison to the other problems on Day1/Day2 (solved it during transfer orientation in about 20 minutes). I guess it comes down to knowing the key lemma, which is somewhat obscure. The answer is $985$. WLOG, by shifting $a_1 = 0$ (clearly $a_1$ isn't forced). Now, we construct regular sequences inductively using the following procedure. Start with the inequality \[ \tfrac01 \le x < \tfrac11. \] Then for each $k = 2, 3, \dots, 1000$ we perform the following procedure. If there is no fraction of the form $F = \frac mk$ in the interval $A \le x < B$, then $a_k$ is forced, and the interval of possible $x$ values does not change. Otherwise, $a_k$ is not forced, and we pick a value of $a_k$ and update the interval accordingly. The theory of Farey sequences tells us that when we have a stage $\tfrac ab \le x < \tfrac cd$ then the next time we will find a fraction in that interval is exactly $\tfrac{a+c}{b+d}$ (at time $k=b+d$), and it will be the only such fraction. So essentially, starting with $\tfrac 01 \le x < \tfrac 11$ we repeatedly replace one of the endpoints of the intervals with the mediant, until one of the denominators exceeds $1000$; we are trying to minimize the number of non-forced terms, which is the number of denominators that appear in this process. It is not hard to see that this optimum occurs by always replacing the smaller of the denominators, so that the sequence is \begin{align*} \tfrac{0}{1} &\le x < \tfrac{1}{1} \\ \tfrac{0}{1} &\le x < \tfrac{1}{2} \\ \tfrac{1}{3} &\le x < \tfrac{1}{2} \\ \tfrac{1}{3} &\le x < \tfrac{2}{5} \\ \tfrac{3}{8} &\le x < \tfrac{2}{5} \\ \tfrac{3}{8} &\le x < \tfrac{5}{13} \end{align*} and so on; we see that the non-forced terms in this optimal configuration are exactly the Fibanocci numbers. There are $15$ Fibanocci numbers less than $1000$, hence the answer $1000 - 15 = 985$.
Pathological
18.05.2019 07:17
Here is a dumber solution for those who aren't clever enough to come up with the above.
We claim that the maximum possible number of forced terms is $985.$ Indeed, this can be obtained by taking the sequence given by $a_i = \left \lfloor \frac{i}{\phi} \right \rfloor,$ where $\phi = \frac{1 + \sqrt5}{2}$ denotes the golden ratio, as noted by v_Enhance above.
We will now show that this is optimal.
To do so, we will make use of the following critical claim.
ClaimCall a sequence $a_1, a_2, \cdots$ of reals $\mathbf{normal}$ if there is a real number $x$ so that $a_i = \left \lfloor ix \right \rfloor$ for all $i \in \mathbb{N}.$ Then, we claim that this sequence is normal if and only if $a_i + a_j \le a_{i+j} \le a_i + a_j + 1$ for all $i, j \in \mathbb{N}.$
ProofThe "only if" direction is immediate from $\left \lfloor a \right \rfloor + \left \lfloor b + \right \rfloor \le \left \lfloor a+b \right \rfloor \le \left \lfloor a \right \rfloor + \left \lfloor b + \right \rfloor + 1,$ which is true for all reals $a, b.$ Now, we will show the "if" direction. We will show by induction on $n$ that if the condition is satisfied for $i+j \le n$, then $a_1, a_2, \cdots, a_n$ is a prefix of a normal sequence, i.e. regular. This would then solve the problem if we let $S_n$ be the set of $x$ for which $a_i = \left \lfloor ix \right \rfloor$ for all $1 \le i \le n$, and using Cantor's Nested Interval Theorem to finish.
When $n = 1$, it's obvious. Assume it holds for $n = k$, i.e., there exists a real number $x$ with $a_i = \left \lfloor ix \right \rfloor$ for $1 \le i \le k.$ If $a_{k+1}$ is uniquely determined by the condition, then we're clearly done, since it must be $\left \lfloor x(k+1) \right \rfloor$, and so $x$ still works for the first $k+1$ terms. Otherwise, we have that $a_1 + a_k = a_2 + a_{k-1} = \cdots = a_k + a_1.$ Then, $a_{k+1}$ is either $a_i + a_{k+1-i}$ or $a_i + a_{k+1-i} + 1.$ We will consider two cases.
$\mathbf{Case}$ $\mathbf{1.}$ $\left \lfloor x(k+1) \right \rfloor = a_i + a_{k+1-i}.$
Then, we only need to show that $a_1, a_2, \cdots, a_k, a_1 + a_k + 1$ is a regular sequence, since $a_1, a_2, \cdots, a_k, a_1 + a_k$ is regular by assumption. Let $c = a_1 + a_k + 1$. Indeed, we claim that taking $y = \frac{c}{k+1}$ works, in the sense that $a_i = \left \lfloor \frac{ci}{k+1} \right \rfloor$ for $1 \le I \le k+1.$ We'll now show this. Notice that $a_i + a_{k+1-i} = c - 1$. If we had that $a_i < \left \lfloor \frac{ci}{k+1} \right \rfloor$, then we'd have $ix < \frac{ci}{k+1} \Rightarrow (k+1-i)x < \frac{c(k+1-i)}{k+1}$, which gives us that $a_{k+1-i} = \left \lfloor (k+1-i)x \right \rfloor \le \left \lfloor \frac{c(k+1-i)}{k+1} \right \rfloor.$ We therefore know that $c - 1 = a_i + a_{k+1-i} < \left \lfloor \frac{ci}{k+1} \right \rfloor + \left \lfloor \frac{c(k+1-i)}{k+1} \right \rfloor \le c.$ Hence, we must have equality everywhere, i.e. $\frac{ci}{k+1}, \frac{c(k+1-i)}{k+1}$ are both integral, $a_i = \left \lfloor \frac{ci}{k+1} \right \rfloor$, and $a_{k+1-i} = \left \lfloor \frac{c(k+1-i)}{k+1} \right \rfloor$. However, since $a_{k+1-i} \le (k+1-i)x < \frac{c(k+1-i)}{k+1},$ this is an impossibility, Therefore, we cannot have that $a_i < \left \lfloor \frac{ci}{k+1} \right \rfloor$. Analogously, we have that $a_{k+1-i} \ge \left \lfloor \frac{c(k+1-i)}{k+1} \right \rfloor,$ which together give that $a_i + a_{k+1-i} \ge \left \lfloor \frac{ci}{k+1} \right \rfloor + \left \lfloor \frac{c(k+1-i)}{k+1} \right \rfloor \ge c - 1.$ Hence, we again have that equality holds everywhere, and so in particular we have that $a_i = \left \lfloor \frac{ci}{k+1} \right \rfloor,$ as desired.
$\mathbf{Case}$ $\mathbf{2.}$ $\left \lfloor x(k+1) \right \rfloor = a_i + a_{k+1-i} + 1.$
This case is basically analogous to Case 1, and will be left as an exercise to the reader.
$\square$
Due to the above claim, we know that $a_n$ is unforced if and only if $a_1 + a_{n-1} = a_2 + a_{n-2} = \cdots = a_{n-1} + a_1,$ for $1 \le n \le 1000.$ Let $x$ be a real number so that $a_i = \left \lfloor ix \right \rfloor$ for $1 \le i \le 1000.$ Consider the sequence $\{b_i\}$ given by $b_i = ix - a_i = ix - \left \lfloor ix \right \rfloor = \{ix\},$ where $\{ \}$ denotes fractional part here. Call an index $1 \le i \le 1000$ $\mathbf{great}$ if $b_i$ is at least as large as each of $b_1, b_2, \cdots, b_{i-1}$, and call it $\mathbf{puny}$ if it is strictly smaller than each of $b_1, b_2, \cdots, b_{i-1}.$ Call any index $1 \le i \le 1000$ which is neither great nor puny $\mathbf{ordinary},$ and other indices $\mathbf{interesting}.$ We claim that every great or puny index is non-forced. Indeed, if $i$ is great, then we have that $a_j + a_{i-j} = ix - \{jx\} - \{(i-j)x\} = ix - \{ix\},$ which is constant over $j$. And if $i$ is puny, then we have that $a_j + a_{i-j} = ix - \{jx\} - \{(i-j)x\} = ix - \{ix\} - 1,$ which is also constant over $j$. Therefore, it suffices to show that at least $15$ indices are either great or puny. First of all, observe that if $m$ is great and $n$ is puny, then we can't have that all of $\max(m, n) + 1, \cdots, m+n$ are ordinary. Indeed, observe that $b_{m+n} = \{ b_m + b_n\},$ which is less than $b_m$ if $b_m + b_n > 1$ and greater than $b_n$ if $b_m + b_n < 1.$ Hence, assuming that $\max(m, n) + 1, \cdots, m+n-1$ are all ordinary, $m+n$ cannot be ordinary. This directly implies the claim. Now, let $1 = n_1 < n_2 < \cdots < n_t\le 1000$ be the interesting numbers. Notice that $1$ is both great and puny simultaneously. We are now ready to show that $n_{i+2} \le n_{i+1} + n_i$ for all $1 \le i \le t-2.$ Indeed, if we let $\alpha$ be the greatest puny interesting number which is $\le n_{i+1}$ and $\beta$ be the greatest great interesting number which is $\le n_{i+1}$, then our lemma shows that $n_{i+2} \le \alpha + \beta.$ Since one of $\alpha, \beta$ is $n_{i+1}$ and the other is not (we're looking at $n_{i+2} \ge n_3$ right now), we've that $n_{i+2} \le n_{i+1} + n_i,$ as claimed. This implies with an easy induction that $n_x \le F_{x+1}$ for all $x$, and so we're done since $F_{16} = 987 < 1000.$
$\square$
Idio-logy
14.10.2020 04:05
Define $F_0 = 0$, $F_1=1$, and $F_k = F_{k-1} + F_{k-2}$. First of all, we describe forced terms in a more straightforward way: $a_k$ is forced if and only if the following inclusion holds \[\varnothing \neq I_{k-1} := \left[a_1,a_1+1\right) \cap \left[\frac{a_2}{2}, \frac{a_2+1}{2}\right) \cap \dots \cap \left[\frac{a_{k-1}}{k-1}, \frac{a_{k-1}+1}{k-1}\right) \subseteq \left[\frac{a_k}{k}, \frac{a_k+1}{k}\right).\]WLOG $0\le a_k \le k-1$ for all $1\le k\le n$, so that $I_k \subseteq [0,1)$. Say $k$ is \emph{separating} if the interval $I_{k-1}$ is not contained in $[a_k/k, (a_k+1)/k)$. Let $I_{k} = [\frac{p_k}{q_k}, \frac{r_k}{s_k})$ in lowest terms, with the convention that $0= \frac{0}{1}$. We will prove the following two claims together using strong induction: Claim 1. For all $k$, we have $r_kq_k - s_kp_k = 1$. Claim 2. For all $k\ge 2$, we have that $k$ is separating if and only if $k = q_{k-1} + s_{k-1}$. Proof. The base case $k=1$ for claim 1 is obvious. We first prove that if claim 1 is true for $k$, then claim 2 is true for $k+1$. We know that $k+1$ is separating if and only if there exists a rational number $\frac{l}{k+1} \in (\frac{p_k}{q_k}, \frac{r_k}{s_k})$. Lemma. Suppose that some rational number in lowest terms $\frac{u}{v} \in (\frac{p_k}{q_k}, \frac{r_k}{s_k})$. Then $v\ge q_k + s_k$. Proof. We have \[uq_k - vp_k \ge 1,\ vr_k - us_k \ge 1,\]which implies \[v \ge \frac{1 + us_k}{r_k} \ge \frac{1+s_k\frac{1+vp_k}{q_k}}{r_k} \implies v \ge \frac{q_k + s_k}{r_kq_k-s_kp_k} = q_k + s_k.\ \square\] If $k+1 = q_k + s_k$, then $k+1$ is separating since the fraction $\frac{p_k+r_k}{k+1} = \frac{p_k+r_k}{q_k+s_k}$ clearly satisfies \[\frac{p_k}{q_k} < \frac{p_k+r_k}{q_k+s_k} < \frac{r_k}{s_k}.\]If $k+1$ is separating, then the lemma implies that $k+1 \ge q_k + s_k$, and the indices $k, k-1, \dots, \max\{q_k,s_k\} + 1$ are not separating. This means that $k+1 = q_k + s_k$, as desired. Next, we prove that if claim 2 is true for $k+1$, then claim 1 is true for $k+1$. If $k+1$ is not separating, then the intervals $I_k = I_{k+1}$, so we are done. If $k+1$ is separating, then clearly \[\frac{p_k+r_k-1}{q_k+s_k} < \frac{p_k}{q_k} < \frac{p_k+r_k}{q_k+s_k} < \frac{r_k}{s_k} < \frac{p_k+r_k+1}{q_k+s_k}\]so $a_{k+1} = p_k + r_k$. This implies that $I_{k+1} = [\frac{p_k}{q_k}, \frac{p_k+r_k}{q_k+s_k})$ or $[\frac{p_k+r_k}{q_k+s_k}, \frac{r_k}{s_k})$, both of which satisfy claim 1. $\square$ For $I_k = [\frac{p_k}{q_k}, \frac{r_k}{s_k})$, we define an unordered pair $J_k = (q_k,s_k)$. The two claims above ensure that given some $J_k = (q_k,s_k)$, the next $J_l$ ($l>k$) different from $J_k$ is \[J_{q_k + s_k} \in \left\{ (q_k,q_k+s_k), (q_k+s_k,s_k) \right\}\]Since we want to maximize the number of indices that are not separating, we want to always choose the pair with larger sum. So the separating indices are exactly the numbers $F_3, F_4, \dots, F_{16} = 987$, which are the 14 Fibonacci numbers in $[2,1000]$. Therefore, the number of forced terms is at most $1000 - 14 - 1 = 985$, and equality can be achieved by choosing \[a_{F_n} = \begin{cases} F_{n-2} & \text{if } n \text{ is odd;}\\ F_{n-2} - 1 & \text{if } n \text{ is even.} \end{cases}\]for all $n\ge 3$.
TheAoPSLebron
14.10.2020 04:05
Why the bump??
InternetPerson10
14.10.2020 04:32
TheAoPSLebron wrote: Why the bump?? it's accepted in HSO (and even in other forums too, i think) to post a full solution to a problem that has appeared in a contest before, like those found in the contest collections.
EthanWYX2009
16.09.2024 18:32
Nice problem! Can be immediately solved by some properties of Farey Sequence and Continued Function(doing approximation).