Proving Open Cup Problem.

Правка en3, от halyavin, 2017-03-07 12:33:16

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. It turns out that f(n) = n + f(k) + f(n − 1 − k) where k = [(n − 1) / 2]. 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 coin

Let us construct the b sequence first.

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 B2 since its sum is less than of equal to n − (a1 + ... + at + 1) ≤ nk − 1 = l since 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 + l ≥ n − 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)). QED.

Piece of convex cake

Теги 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)