返回题库

HMMT 二月 2017 · 冲刺赛 · 第 17 题

HMMT February 2017 — Guts Round — Problem 17

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 10 ] Sean is a biologist, and is looking at a string of length 66 composed of the letters A, T, C, G . Asubstring of a string is a contiguous sequence of letters in the string. For example, the string AGT C has
    10 substrings: A, G, T, C, AG, GT, T C, AGT, GT C, AGT C. What is the maximum number of distinctsubstrings of the string Sean is looking at?
解析

英文解析

  1. [ 10 ] Sean is a biologist, and is looking at a string of length 66 composed of the letters A, T, C, G . Asubstring of a string is a contiguous sequence of letters in the string. For example, the string AGT C has
    10 substrings: A, G, T, C, AG, GT, T C, AGT, GT C, AGT C. What is the maximum number of distinctsubstrings of the string Sean is looking at?
    Proposed by: Yang Liu
    Answer: 2100
    Let’s consider the number of distinct substrings of length . On one hand, there are obviously at most
    4 distinct substrings. On the other hand, there are 67 − ` substrings of length ` in a length 66 string.
    Therefore, the number of distinct substrings is at most
    ∑66
    min(4 , 67 − ) = 2100 .
    ` =1
    To show that this bound is achievable, one can do a construction using de brujin sequences that wewon’t elaborate on here.