The problem D in the latest Open Cup involves function *f*(*n*) which is defined as the minimum sum of sequence *b*_{1}, ..., *b*_{k} such that any sequence *a*_{1}, ..., *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*_{1} be a sequence that covers all sequences with sum less than or equal to *k*. Let *B*_{2} be a sequence that covers all sequences with sum less than or equal to *l*. Let *n* = *k* + *l* + 1. Then sequence *B*_{1}, *n*, *B*_{2} covers all sequences with sum less than or equal to *n*.

*Proof*. Let *a*_{1}, ..., *a*_{s} be a sequence with sum less than or equal to *n*. Let *t* be the largest index such that *a*_{1} + ... + *a*_{t} ≤ *k*. Then the first *t* elements of sequence *a* can be dominated by some subsequence of *B*_{1}. 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*_{2} since its sum is less than of equal to *n* − (*a*_{1} + ... + *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*_{1} = *n* and so must have element greater than or equal to *n*.

**Theorem 2.** Let *B* = *B*_{1}, *m*, *B*_{2} 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*_{1}. Let *l* be the largest number such that all sequences with sum less than of equal to *l* are covered by *B*_{2}. Then *k* + *l* ≥ *n* − 1.

*Proof*. Assume *k* + *l* ≤ *n* − 2. By definition of *k* there is sequence *A*_{1} with sum *k* + 1 which is not covered by *B*_{1}. By definition of *l* there is sequence *A*_{2} with sum *l* + 1 which is not covered by *B*_{2}. Let us consider sequence *A*_{1}, *A*_{2}. It has sum *k* + 1 + *l* + 1 ≤ *n*. Since *A*_{1} is not covered by *B*_{1}, the latest element of *A*_{1} must be covered by *m* or element to the right of it. By the same logic, the first element of *A*_{2} must be covered by *m* or element to the left of it. But the latest element of *A*_{1} must be covered by element of *B* to the left of element covering the first element of *A*_{2}. 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.**

- For all
*n*≥ 1.*f*(*n*) =*n*+*f*(*k*) +*f*(*n*− 1 −*k*) where*k*= [(*n*− 1) / 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* = 2*t*, *t* ≥ 1. The first difference is equal to *f*(*m* + 1) − *f*(*m*) = (*m* + 1 + 2*f*(*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 + 2*f*(*t* − 1)) = 1 + *f*(*t*) − *f*(*t* − 1). The differences coincide which proves the second statement.

Second case. *m* = 2*t* + 1, *t* ≥ 1. The first difference is equal to *f*(*m* + 1) − *f*(*m*) = (*m* + 1 + *f*(*t* + 1) + *f*(*t*)) − (*m* + 2*f*(*t*)) = 1 + *f*(*t* + 1) − *f*(*t*). The second difference is equal to *f*(*m*) − *f*(*m* − 1) = (*m* + 2*f*(*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.