This puzzle is the fourteenth puzzle from the Matt Parker's Maths Puzzles series.
If you have four cards numbered 1 to 4, how many of the 24 permutations contain no subsequence of length three that is increasing or decreasing?
Since there are only 24 different permutations, checking them with a brute force is viable. For each permutation, we count the length of the longest increasing subsequence, and the length of the longest decreasing subsequence, and if they are both less than three we can increment our counter.
Finding the length of the longest increasing subsequence can be done as follows with a dynamic programming style solve:
from bisect import bisect
def longestIncreasing(sequence):
"""
Calculates the length of the longest increasing subsequence of a given
sequence.
"""
dp = [sequence[0]]
for v in sequence:
try:
# bisect will do a binary search for the insertion index in dp such
# that dp stays sorted
dp[bisect(dp, v)] = v
except IndexError:
dp.append(v)
return len(dp)for each value in the sequence, we have to do a binary search on the dp array, whose length is bounded by the length of the sequence, giving us a runtime complecity of O(n log(n)).
Finding the length of the longest decreasing sequence is the same as finding the length of the longest increasing sequence of the sequence whose values have been negated.
We can now implement our brute force solution:
from itertools import permutations
def countSpikeyPermutations(n, k):
"""
Counts how many permutations of the integers 1 to n contain no monotonic
subsequences that are of length k or more.
"""
result = 0
for p in permutations(range(n)):
if all(
longestIncreasing(sequence) < k
for sequence in (p, map(lambda x: -x, p))
):
result += 1
return resultSince there are n! different permutations, and we are calculating the lenth of the longest increasing and decreasing subseques for each of them, our total runtime complexity will be O(n!*n*log(n)). This will not scale well (it is bearable up to n ≈ 9), but we find that the number of permutations with no monotonic subsequences of length 3 or more is 4. And they are:
- 2, 1, 4, 3.
- 2, 4, 1, 3.
- 3, 1, 4, 2.
- 3, 4, 1, 2.
If you have ten cards numbered 1 to 10, it is possible to avoid containing a monotonic subsequence of lenth 8 with the permutation:
- 10, 2, 3, 4, 6, 5, 7, 8, 9, 1.
What is the largest k, such that every permutation is guaranteed to have either an increasing or decreasing subsequence of length k or more?
Firstly, we can repurpose our original code to have an algorithm with the same runtime complexity:
def maxUnavoidable(n):
"""
Calculates the maximum k such that all permutations of the integers 1 to n
must contain either an increasing or decreasing subsequence of length k or
more.
"""
return min(max(
longestIncreasing(sequence)
for sequence in (p, map(lambda x: -x, p))
) for p in permutations(range(n)))This takes quite a while (calculating it on my computer took more than 30 seconds) but I was able to calculate the value of the maximum k for the first 10 integers, the number of permutations that avoid any monotonic subsequences with a length more than k + 1, and an example of one of these "optimal" permutations not containing such a subsequence:
| n | max k | num avoiding k + 1 | example "optimal" permutation |
|---|---|---|---|
| 3 | 2 | 4 | 0, 2, 1 |
| 4 | 2 | 4 | 1, 0, 3, 2 |
| 5 | 3 | 86 | 0, 1, 4, 3, 2 |
| 6 | 3 | 306 | 2, 1, 4, 3, 0, 5 |
| 7 | 3 | 882 | 2, 5, 6, 0, 3, 1, 4 |
| 8 | 3 | 1764 | 3, 2, 5, 0, 7, 4, 6, 1 |
| 9 | 3 | 1764 | 3, 7, 2, 0, 8, 5, 6, 1, 4 |
| 10 | 4 | 985032 | 3, 8, 4, 0, 2, 7, 5, 1, 9, 6 |
We can see that the max k increases after 4 and after 9. This led me to the following proposition:
The largest k, such that every permutation of 1, ..., n is guaranteed to have either an increasing or decreasing subsequence of length k or more is bounded above by one more than the square root of n.
We can prove this by constructing a permutation that avoids monotonic subsequences longer than the square root of p.
Let p be the smallest integer greater than or equal to the square root of n. If we take the numbers from 1 to n in order, we can reverse the sections 1 to p, p + 1 to 2p and so on until we reverse (p - 1)p to n to create a new permutation.
.
.
.
.
.
.
.
.
An illustration of the scheme for n = 8.
We claim the the longest monotone subsequence has length p. Any decreasing subsequence can be no longer than p, as it must be completely contained in one of the groups. Any increasing subsequence can be no longer than p, as it cannot use more than one element from any of the groups. ☐
The largest k, such that every permutation of 1, ..., n is guaranteed to have either an increasing or decreasing subsequence of length k or more is bounded below by the square root of n.
Fix a permutation, P, of the numbers 1 to n. For each 1 ≤ i ≤ n, we can define two numbers A(i) and D(i) where A(i) is the length of the longest increasing subsequence in P(1), P(2), ..., P(i) and and D(i) is the length of the longest decreasing subsequence in P(1), P(2), ..., P(i). We show that for every i, the pair A(i), D(i) must be unique.
Fix 1 ≤ x ≤ n. Assume that there exists some y < x such that A(y) = A(x) and D(y) = D(x). Since P is a permutation, we have P(x) ≠ P(y).
Suppose that P(y) < P(x), then there is an increasing subsequence of P(1), ..., P(y) that is increasing and has length A(y). Since P(y) < P(x) we can append x to this subsequence to generate an increasing subsequence of P(1), ..., P(x) of length A(y) + 1, but A(y) = A(x) ≥ A(y) + 1 is a contradiction.
Suppose that P(y) > P(x), then in the same manner as before, we can use a decreasing subsequence of P(1), ..., P(y) of length D(y) to produce a decreasing subsequence of P(1), ..., P(x) of length D(y) + 1, but D(y) = D(x) ≥ D(y) + 1 is a contradiction.
Therefore no such y exists, and the pair A(i), D(i) is unique for each i. We can now use the pigeon-hole principal to see that P must contain either an increasing or decreasing subsequence of the square root of n or more, since the number of unique pairs of integers bounded by b is b^2. ☐
Finishing up: Erdős–Szekeres theorem
We can now combine these propositions to form the theorem: The largest k such that every permutation of 1 to n must contain a monotonic subsequence of length k is the ceiling of the square root of n.
Firstly k must be an integer, and must be contained in [sqrt(n), sqrt(n) + 1], this is precisely the ceiling function on sqrt(n).
And now we can change our python code!
def maxUnavoidable(n):
"""
Calculates the minimum k such that all permutations of the integers 1 to n
must contain either an increasing or decreasing subsequence of length k or
more.
"""
return ceil(sqrt(n))Much faster!