1305번 - 광고
가능한 광고의 길이 중 가장 짧은 길이를 N, W(A)를 A의 접두사와 접미사가 같으면서 가장 긴 non-trivial 문자열의 길이라고 하겠습니다.
Claim: |A| - W(A) = N
A - W(A) <= N 증명은 간단하므로 생략합니다.
만약 |B| < |A| 이고 A^inf = B*inf 인 문자열 B가 존재한다면
A^inf <= B^inf iff A <= BA^inf >= B^inf iff A >= B
이나 |B| < |A| 이기 때문에 위 두 조건을 동시에 만족할 수 없으므로 모순입니다. 그러한 더 짧은 문자열 B는 존재하지 않습니다.
이와 비슷한 증명 문제로 도도의 수학놀이, 큰 수 만들기 문제 등이 있습니다.
제가 수학을 잘 모르는데, 길이가 무한한 문자열끼리 대소비교가 가능한가요?
댓글을 작성하려면 로그인해야 합니다.
some256 4년 전 1
가능한 광고의 길이 중 가장 짧은 길이를 N, W(A)를 A의 접두사와 접미사가 같으면서 가장 긴 non-trivial 문자열의 길이라고 하겠습니다.
Claim: |A| - W(A) = N
A - W(A) <= N 증명은 간단하므로 생략합니다.
만약 |B| < |A| 이고 A^inf = B*inf 인 문자열 B가 존재한다면
A^inf <= B^inf iff A <= B
A^inf >= B^inf iff A >= B
이나 |B| < |A| 이기 때문에 위 두 조건을 동시에 만족할 수 없으므로 모순입니다. 그러한 더 짧은 문자열 B는 존재하지 않습니다.
이와 비슷한 증명 문제로 도도의 수학놀이, 큰 수 만들기 문제 등이 있습니다.