April 22, 2020
Problem statement:
Let X be a set of strings, each of length at least 6, using letters A, B, C, ..., Z (letters may be repeated). What is the least number of elements that X must contain in order to guarantee that two elements of X have the same fourth letter and the same sixth letter? For example, the settings PIGEON and CAVERN both have fourth letter E and six letter N.
How to solve the problem?
It is not an easy problem. Let me walk through the simple problem first, how to solve one by one, and then work on specific case 4th and 6th letter.
Question 1: Any number at least six letters - minimum number of elements; all digits should be same to treat as duplicate.
It is easy to figure out, each digit has 26 choices, so the first six digits have 26^6 options. The answer should be 26^6 + 1 = 308915777
Question 2: Any number at least six letters - minimum number of elements, fourth letter should be different.
Answer:
4th digit
A
B
...
Z
The answer should be 26 + 1 = 27, for each 4th digit, all other 5 digits should have one option.
Since AAAAAA is duplicate as BBBABB
4 4
Question 3: Any number at least six letters - 4th letter and 6th letter should not duplicate.
Let us brute force all possible options for 4th and 6th two digits.
Let us put together a table:
Case 1:
4th 6th
A A
A B
A C
...
A Z
Case 2:
4th 6th
B A
B B
B C
...
B Z
...
Case 26
4th 6th
Z A
Z B
...
Z Z
For 4th and 6th digits have 26 * 26 option, for each option of the above 26 * 26, there is only one option for 1th, 2th, 3th, 5th digit. Otherwise, we count them as duplicate.
For example, 4th A, 6th A, we can only have one word, any letter for 1th, 2th, 3th, 5th, for keeping one option, AAAAAA and BBBABA would be duplicate since first word 4th and 6th letter are both 'AA'.
Based on the above analysis, we argue that least number to contain duplicate 4th and 6th digits should be 26^2 + 1 = 677.
Any feedback. It is tough for me to warm up the algorithm.
No comments:
Post a Comment