A Problem of Satisfying Inequalities

James Tanton has recently tweeted the following problem:

Is it always possible to replace the (10) X's in the expression X > X > X < X < X > X < X < X > X < X with numbers 1, ..., 10 so that inequality signs be respected.

Solution

Is it always possible to replace the (10) X's in the expression X > X > X < X < X > X < X < X > X < X with numbers 1, ..., 10 so that inequality signs be respected.

The answer is Yes, and the induction seems to be a suitable tool to tackle this problem. To see that, let's first agree to replace the inequality signs with a more generic symbol, say "?".

Second, observe, that the problem of replacing the X's with integers 1, 2, ..., n is equivalent to that of replacing the X's with members of an arbitrary increasing sequence a₁ < a₂ < ... < a_n. Indeed, if the expression

α₁ ? α₂ ? ... ? α_n

where α's are distinct members of {1, ..., n} then also

a_α₁ ? a_α₂ ? ... ? a_{α_n},

and vice versa. This is so because, when the sequence {a_k} is increasing, the inequality m < n is equivalent to a_m < a_n.

The induction is on the number N of the inequality signs. The statement is obvious for N = 1.

Assume it holds for k = m and let's show that it then holds for k = m + 1. Given an expression X?X?...?X with m + 1 inequality signs, remove the last one and the terminating X. The remaining expression contains m inequality signs and is, therefore, under the inductive hypothesis, solvable. In other words, integers 1 through m can replace the m remaining X's so that all (m-1) inequalities be satisfied.

The next step depends on whether the removed inequality sign is "<" or ">". In the former case all we have to do is to replace the last X with m + 1. In the latter case, we fill the shortened expression X?X?...?X with integers from the set {2, 3, ..., m + 1}, and then replace the last X with 1.

72365655