The problem D in the latest Open Cup involves function f(n) which is defined as the minimum sum of sequence b₁, ..., b_k such that any sequence a₁, ..., a_l with sum less than or equal to n can be dominated by some subsequence of b. One sequence dominates the other, if they have the same length any every element of the first sequence greater than or equal to corresponding element of the second sequence. It turns out that f(n) = n + f(k) + f(n − 1 − k) where k = [(n − 1) / 2]. But why? If this equation still keeps you up at night, you can finally sleep well now. I have found a wonderful proof of this statement which fits the bounds of this site.

Two sides of the proof

Let us construct the b sequence first.

For brevity, we will say that sequence b covers sequence a, if some subsequence of b dominates a.

Theorem 1. Let B₁ be a sequence that covers all sequences with sum less than or equal to k. Let B₂ be a sequence that covers all sequences with sum less than or equal to l. Let n = k + l + 1. Then sequence B₁, n, B₂ covers all sequences with sum less than or equal to n.

Proof. Let a₁, ..., a_s be a sequence with sum less than or equal to n. Let t be the largest index such that a₁ + ... + a_t ≤ k. Then the first t elements of sequence a can be dominated by some subsequence of B₁. If t = s we don't need to go any further. Otherwise, the element a_t + 1 can be dominated by n and the rest of the sequence can be dominated by a subsequence of B₂ since its sum is less than of equal to n − (a₁ + ... + a_t + 1) ≤ n − k − 1 = l where we used that the sum of first t + 1 elements of a is strictly greater than k by definition of t.

From Theorem 1 follows that f(n) ≤ min_k(n + f(k) + f(n − 1 − k)).

Simple enough, but how to prove the lower bound?

First of all, any covering sequence must cover sequence with single element a₁ = n and so must have element greater than or equal to n.

Theorem 2. Let B = B₁, m, B₂ be an arbitrary split of a sequence that covers all sequences with sum less than or equal to n. Let k be the largest number such that all sequences with sum less than or equal to k are covered by B₁. Let l be the largest number such that all sequences with sum less than of equal to l are covered by B₂. Then k + l ≥ n − 1.

Proof. Assume k + l ≤ n − 2. By definition of k there is sequence A₁ with sum k + 1 which is not covered by B₁. By definition of l there is sequence A₂ with sum l + 1 which is not covered by B₂. Let us consider sequence A₁, A₂. It has sum k + 1 + l + 1 ≤ n. Since A₁ is not covered by B₁, the latest element of A₁ must be covered by m or element to the right of it. By the same logic, the first element of A₂ must be covered by m or element to the left of it. But the latest element of A₁ must be covered by element of B to the left of element covering the first element of A₂. We arrive at the contradiction and so k + l ≥ n − 1.

If we split the sequence B at element greater than or equal to n, from Theorem 2 follows f(n) ≥ n + f(k) + f(l) where k + l ≥ n − 1. Since f(n) is non-decreasing we can set l = n − 1 − k and get f(n) ≥ min_k(n + f(k) + f(n − 1 − k)).

Combining results from both theorems, we have f(n) = min_k(n + f(k) + f(n − 1 − k)). Q.E.D.

Piece of convex cake

But, sir, you have got the wrong formula. The only way they can be the same, if minimum over k is always happens to be in the middle. Like in the case of convex functions. Well, let us prove f(n) is convex then. Stay back, I am going to use induction.

Theorem 3.

1. For all n ≥ 1. f(n) = n + f(k) + f(n − 1 − k) where k = [(n − 1) / 2].
2. For all n ≥ 2. f(n) − f(n − 1) ≥ f(n − 1) − f(n − 2).

Proof. We have f(0) = 0, f(1) = 1, f(2) = 3 which prove the theorem for n ≤ 2. We have the basis of induction, now let us prove the induction step. Assume the theorem is proved for all n ≤ m. Let us prove it for n = m + 1.

The first statement is the consequence of the second for n ≤ m. If k + 1 ≤ m − (k + 1), we have f(k) + f(m − k) = f(k) + f(m − (k + 1)) + (f(m − k) − f(m − (k + 1))) ≥ f(k) + f(m − (k + 1)) + (f(k + 1) − f(k)) = f(k + 1) + f(m − (k + 1)). So if we increase k starting from 1, the sum f(k) + f(m − k) decreases or stays the same until k = [m/2].

In order to prove the second statement, we need to consider two cases.

First case, m = 2t, t ≥ 1. The first difference is equal to f(m + 1) − f(m) = (m + 1 + 2f(t)) − (m + f(t) + f(t − 1)) = 1 + f(t) − f(t − 1). The second difference is equal to f(m) − f(m − 1) = (m + f(t) + f(t − 1)) − (m − 1 + 2f(t − 1)) = 1 + f(t) − f(t − 1). The differences coincide which proves the second statement.

Second case. m = 2t + 1, t ≥ 1. The first difference is equal to f(m + 1) − f(m) = (m + 1 + f(t + 1) + f(t)) − (m + 2f(t)) = 1 + f(t + 1) − f(t). The second difference is equal to f(m) − f(m − 1) = (m + 2f(t)) − (m − 1 + f(t) + f(t − 1)) = 1 + f(t) − f(t − 1). The first difference is greater than or equal to the second due to induction assumption for t + 1 ≤ m which we can apply since t + 1 ≥ 2.

This completes the proof of the theorem and allows us to remove min from the formula.