Proving Open Cup Problem.

Правка en6, от halyavin, 2017-03-07 23:40:04

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

Proof. Let a1, ..., as be a sequence with sum less than or equal to n. Let t be the largest index such that a1 + ... + atk. Then the first t elements of sequence a can be dominated by some subsequence of B1. If t = s we don't need to go any further. Otherwise, the element at + 1 can be dominated by n and the rest of the sequence can be dominated by a subsequence of B2 since its sum is less than of equal to n − (a1 + ... + at + 1) ≤ nk − 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) ≤ mink(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 a1 = n and so must have element greater than or equal to n.

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

Proof. Assume k + ln − 2. By definition of k there is sequence A1 with sum k + 1 which is not covered by B1. By definition of l there is sequence A2 with sum l + 1 which is not covered by B2. Let us consider sequence A1, A2. It has sum k + 1 + l + 1 ≤ n. Since A1 is not covered by B1, the latest element of A1 must be covered by m or element to the right of it. By the same logic, the first element of A2 must be covered by m or element to the left of it. But the latest element of A1 must be covered by element of B to the left of element covering the first element of A2. We arrive at the contradiction and so k + ln − 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 + ln − 1. Since f(n) is non-decreasing we can set l = n − 1 − k and get f(n) ≥ mink(n + f(k) + f(n − 1 − k)).

Combining results from both theorems, we have f(n) = mink(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 nm. Let us prove it for n = m + 1.

The first statement is the consequence of the second for nm. If k + 1 ≤ m − (k + 1), we have f(k) + f(mk) = f(k) + f(m − (k + 1)) + (f(mk) − 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(mk) 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.

Теги opencup

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский halyavin 2017-03-07 23:40:04 4 (published)
en5 Английский halyavin 2017-03-07 23:39:19 420 Fix text.
en4 Английский halyavin 2017-03-07 13:32:41 3155 Second part.
en3 Английский halyavin 2017-03-07 12:33:16 4318 Main proofs
en2 Английский halyavin 2017-03-07 11:43:37 84 Fix formating.
en1 Английский halyavin 2017-03-07 11:39:17 1123 Initial revision (saved to drafts)