A finite list of rational numbers is written on a blackboard. In an operation, we choose any two numbers $a$, $b$, erase them, and write down one of the numbers \[ a + b, \; a - b, \; b - a, \; a \times b, \; a/b \text{ (if $b \neq 0$)}, \; b/a \text{ (if $a \neq 0$)}. \] Prove that, for every integer $n > 100$, there are only finitely many integers $k \ge 0$, such that, starting from the list \[ k + 1, \; k + 2, \; \dots, \; k + n, \] it is possible to obtain, after $n - 1$ operations, the value $n!$.
Problem
Source: 7th RMM 2015, Problem 3
Tags: combinatorics proposed, combinatorics, RMM, algebra, algebra proposed
01.03.2015 12:34
We use a proof by contradiction. Fix $n$. Firstly, note that there are only finitely many sequences of operations to reduce this list of $n$ numbers to one using the given allowed operations; you pick from at most $\binom{n}{2}$ pairs of numbers and one of $6$ operations each time, so there are far less than $\left(6\binom{n}{2}\right)^{n-1}$ possible sequences. So, if there are infinitely many integers $k$ such that $n!$ can be obtained from the numbers $k + 1, \ldots, k + n$, then at least one such sequence of operations works for infinitely many integers $k$. But now treat $k$ as an indeterminate and apply the sequence of operations to $k+1, k+2, \ldots, k+n$ to get a rational function $f$ of $k$. This rational function is equal to the constant $n!$ for infinitely many $k$, which means it can only be the constant polynomial $n!$. In particular, $f(k) = n!$ for integers $k$ satisfying $-n \leq k \leq -1$. However: Lemma. It is impossible for any sequence of operations to produce $n!$ from the list of integers $k + 1, \ldots, k+n$ for integer $k$ such that $-n \leq k \leq -1$. Proof. Consider the function $w$ defined as such: for a fraction $p/q$ written in lowest terms, $w(p/q) = |p| + |q|$. Then if $a$ and $b$ are combined through any operation to get $c$, we may verify that $w(c) \leq w(a)w(b)$. So the product of $w(x)$ across all $x$ on the blackboard is nonincreasing, a monovariant. But for $k$ satisfying $-n \leq k \leq -1$, since $k + 1 \leq 0$ and $k + n \geq 0$, the initial value of this monovariant is \begin{align*} w(k+1)w(k+2)\cdots w(k+n) &= (|k+1|+1)(|k+2|+1)\cdots(|k+n|+1) \\ &= (-k)!(k+n+1)! \\ &= \frac{(n+1)!}{\binom{n+1}{-k}} \\ &\leq \frac{(n+1)!}{n+1} \\ &= n!. \end{align*} So, since \[w(n!) = w(n!/1) = n! + 1 > n!, \] it is impossible to obtain $n!$ for any of the $n$ values of $k$ in the range $-n \leq k \leq -1$. -- end proof -- Unfortunately, this is not the contradiction we want yet, because it's possible that the sequence of operations, when applied to such a list, resulted in a division by zero that was masked by some factor being cancelled from the numerator and denominator in the process of calculating $f$. Still, we are quite close. (I'm somewhat expecting there's a simple way to finish at this point that I'm overlooking...) Let's calculate $f$ by applying the sequence of operations to the list, but without ever cancelling factors from the numerator and denominator, to get a fraction of polynomials $P(k)/Q(k)$. The result has to be the constant term $n!$ after cancelling common factors as above, but since we've proved in the lemma that the operations cannot produce $n!$ for $n$ values of $k$, that means $Q(k)$ must be zero for these $n$ values. $Q(k)$ certainly can't be constantly zero because the sequence of operations still has to work for infinitely many nonnegative values of $k$, so $Q(k)$ has degree at least $n$. We now just have to prove this is impossible. For a "generalized rational function" $P(x)/Q(x)$ where $P$ and $Q$ may have common factors, denote $s(P(x)/Q(x)) = \max(\deg P, \deg Q)$. Then, similar to the above, verify that if two "generalized" rational functions $A$ and $B$ are combined with any operation to get $C$ without cancelling factors, we have $s(C) \leq s(A) + s(B)$, so the sum of $s(F)$ across all polynomials $f$ on the blackboard is nonincreasing, a monovariant. We start with $n$ linear functions $k+i$, each of which satisfies $s(k+i) = 1$, so the initial value of the monovariant is $n$. We must produce a ratio of polynomials $P(k)/Q(k)$ where $Q$ has degree at least $n$, so $s(P(k)/Q(k)) \geq n$. This is just barely possible. However, obviously the sequence of operations can't be "multiply everything", since that doesn't produce $n!$ even for $k = 1$, and the resulting ratio of polynomials has constant denominator $1$. And we can also verify that the monovariant must strictly decrease when the first operation that isn't a multiplication is applied. Therefore, there is no way to produce a ratio of polynomials where the denominator has degree at least $n$, so all of the above is impossible, and we are done.
01.03.2015 15:59
math_explorer wrote: I'm somewhat expecting there's a simple way to finish at this point that I'm overlooking... Based on what I've heard from people being in general not too happy with this problem (and I guess from you being pretty good), I'm guessing this is not the case. The consensus seems to be that the "rational function" idea is the only redeeming part of the solution to this problem. EDIT: To clarify, I'm trying to say that the second half of the solution is probably going to be ugly regardless of how you do it, because no one I talked to found a nice way to complete the solution after noticing the "rational function" part.
01.03.2015 18:20
How would you rate this in difficulty on the IMO?
01.03.2015 18:27
Seems very hard for a IMO #2 but relatively easy for IMO #3 (Not nearly as hard as last year's IMO #6 and definitely no the legendary IMO #6's like 2009)
01.03.2015 18:52
mssmath wrote: Seems very hard for a IMO #2 but relatively easy for IMO #3 (NOWHERE near last year's IMO #6) It is an RMM 3 I personally think this problem is comparable to (in fact slightly easier than) last year's IMO #6 though (the solution to last year's IMO #6 is just greedy, and part of the reason people didn't solve it was because it was easy to spend a lot of time on IMO 2014/5). Previous IMO #6's like 2009 and 2011 are certainly much harder than this problem, I think.
01.03.2015 18:54
This problem is really combinatorics? Correct me if I'm wrong, but it looks like an algebra.
01.03.2015 18:55
...and then I see it. I'm not sure if it doesn't count as "ugly" any more, but it was right there all along o_O (I hope this is correct) Substitute, say, the indeterminate $x = k + 50$. For a "generalized rational function" $P(x)/Q(x)$ where $P$ and $Q$ may have common factors, consider the function $v(P(x)/Q(x))$ defined as the sum of the absolute values of the coefficients of every term in $P$ and in $Q$. Verify that if two "generalized" rational functions $A$ and $B$ are combined with any operation to get $C$ without cancelling factors, we have $v(C) \leq v(A)v(B)$, so the product of $v(F)$ across all rational functions $F$ on the blackboard is nonincreasing, a monovariant. (We have to avoid canceling out factors for an entirely different reason this time: doing so can increase the monovariant! e.g. canceling $x - 1$ from $x^4 - 1$ gets $x^3 + x^2 + x + 1$) If there's a sequence of operations that results in the constant $n!$ from the list $k + 1, \ldots, k+n$ for infinitely many $k$, then it results in a generalized rational function that simplifies to the constant $n!$ when applied to the list of rational functions $x - 49, \ldots, x + (n - 50)$. But the list has initial monovariant value $\frac{51! \cdot (n-48)!}{2} \ll n! + 1$, and the rational function that would simplify to $n!$ necessarily has a term with coefficient $n!$ in its numerator, so its monovariant value would be at least $n! + 1$ and we have the contradiction we want.
01.03.2015 19:11
MathPanda1 wrote: This problem is really combinatorics? Correct me if I'm wrong, but it looks like an algebra. We can tag it as algebra too It's admittedly a bit of a fine line; the bounding is quite algebraic but the idea of looking at rational functions to capture the "infinitely many" part of the process is quite combinatorial IMO.
01.03.2015 22:21
v_Enhance wrote: EDIT: To clarify, I'm trying to say that the second half of the solution is probably going to be ugly regardless of how you do it, because no one I talked to found a nice way to complete the solution after noticing the "rational function" part. I disagree with v_Enhance above a lot. My solution for this problem while I took it live was rather clean. (Jack Gurev and Andrew He did the same thing I believe). Given a polynomial $P$, define $g(P)$ to the sum of the absolute value of the coefficients. It is clear that $g(P+Q) \le g(P)+g(Q), g(PQ) \le g(P)g(Q)$. For a rational function, define $f(P/Q) = g(P)+g(Q)$. Throughout this proof, never simplify denominators or anything. Let $S$ be the set of rational functions on the blackboard. I claim that $\prod_{s \in S} f(s)$ is a nonincreasing monovariant, i.e. after each operation, this value never increases. This is trivial to prove: I'll just run it through for addition ($P, Q, R, S$ are polynomials): \begin{align*} f(P/Q+R/S) &= f((PS+RQ)/(QS)) \\ &= g(PS+RQ)+g(QS) \\ &\le g(P)g(S)+g(R)g(Q)+g(Q)g(S) \\ &\le (g(P)+g(Q))(g(R)+g(S)) \\ &= f(P/Q)f(R/S). \end{align*} Let $s$ be the rational function on the board after $n-1$ operations. If it is identically $n!$, obviously $f(s) \ge n!$ because even if you don't simplify, the numerator will have a coefficient at least $n!$ somewhere. So our final trick is to shift $k \rightarrow k-\lfloor n/2 \rfloor$. So the funcitons on the board are now $k - \lfloor n/2 \rfloor + 1, k - \lfloor n/2 \rfloor + 2, \dots, k - \lfloor n/2 \rfloor + n$. Then \[ \prod_{s \in S} f(s) < ((n/2 + 3)!)^2 < n! \] for large enough $n$. You don't really need any sort of ugly bounding.
02.03.2015 04:03
mathocean97 wrote: I disagree with v_Enhance above a lot. My solution for this problem while I took it live was rather clean. (Jack Gurev and Andrew He did the same thing I believe). Given a polynomial $P$, define $g(P)$ to the sum of the absolute value of the coefficients. ... Ah, that's a lot cleaner than things I had heard. I think you're probably right; I take back what I said.
02.03.2015 05:04
Jack Gurev showed me a problem similar to this, except harder. What is the greatest number, in terms of n, that can be created by following the procedure of the original problem?
02.03.2015 05:37
My solution (which is essentially Yang's but worse) Do the reduction to a polynomial identity. Now, define the constant term of a rational function $P(k)/Q(k)$ to be the quotient of the constant terms of $P$ and $Q$ when we divide by factors of $k$ which are present on both the top and bottom. Let the function $I$ be the product over all constant terms of rational functions on the blackboard of the maximum of the absolute values of the numerator and denominator. It is clear that multiplication and subtraction cannot increase $I$, and addition and subtraction can change it by a factor of at most $2$ because $max(|ad|+|bc|,|bd|)\leq 2max(|a|,|b|)max(|c|,|d|)$. Therefore, at the end of the $n-1$ moves $I$ has increased by a factor of at most $2^{n-1}$. Now, perform a shift by $\lceil n/2\rceil$ to the left, so that our rational functions in $k$ are now rational functions in $l=k+\lceil n/2 \rceil$. Then if at the end $I$ is $n!$, the ratio of $I$ at the end to at the beginning is ${n \choose {\lceil{n/2}\rceil}}{\lceil{n/2}\rceil}$. But it is a simple exercise in bounding that this is bigger than $2^{n-1}$ when $n$ is large, so we are done.