HMMT 二月 2005 · 冲刺赛 · 第 45 题
HMMT February 2005 — Guts Round — Problem 45
题目详情
- A binary word is a finite sequence of 0’s and 1’s. A square subword is a subsequence consisting of two identical chunks next to each other. For example, the word 100101011 contains the square subwords 00, 0101 (twice), 1010, and 11. Find a long binary word containing a small number of square subwords. Specifically, write down a binary word of any length n ≤ 50. Your score will be max { 0 , n − s } , where s is the number of occurrences of square subwords. (That is, each different square subword will be counted according to the number of times it appears.) 7
解析
- A binary word is a finite sequence of 0’s and 1’s. A square subword is a subsequence consisting of two identical chunks next to each other. For example, the word 100101011 contains the square subwords 00, 0101 (twice), 1010, and 11. Find a long binary word containing a small number of square subwords. Specifically, write down a binary word of any length n ≤ 50. Your score will be max { 0 , n − s } , where s is the number of occurrences of square subwords. (That is, each different square subword will be counted according to the number of times it appears.) Remark: See http://www.combinatorics.org/Volume 10/PDF/v10i1r12.pdf for analysis of this problem. The maximum possible score is on the order of 25. In general, the minimum number of square subwords of a word of length n tends to roughly 0 . 551 n as n → ∞ . 18