Proving Open Cup Problem.

Revision en1, by halyavin, 2017-03-07 11:39:17

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(nk — 1) 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.

Theorem 1. Let B1 be a sequence that covers all sequences with sum less than or equal to k. LetB2 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 of equal to n.

Tags opencup

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English halyavin 2017-03-07 23:40:04 4 (published)
en5 English halyavin 2017-03-07 23:39:19 420 Fix text.
en4 English halyavin 2017-03-07 13:32:41 3155 Second part.
en3 English halyavin 2017-03-07 12:33:16 4318 Main proofs
en2 English halyavin 2017-03-07 11:43:37 84 Fix formating.
en1 English halyavin 2017-03-07 11:39:17 1123 Initial revision (saved to drafts)