Maths Olympiad Prep

Library / /326 of 377

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

All the sequences consisting of five letters from the set {T,U,R,N,I,P}\{T, U, R, N, I, P\} (with repetitions allowed) are arranged in alphabetical order in a dictionary. Two sequences are called "anagrams" of each other if one can be obtained by rearranging the letters of the other. How many pairs of anagrams are there that have exactly 100 other sequences between them in the dictionary?

Solution

Solution:

Convert each letter to a digit in base 66: I0I \mapsto 0, N1N \mapsto 1, P2P \mapsto 2, R3R \mapsto 3, T4T \mapsto 4, U5U \mapsto 5. Then the dictionary simply consists of all base-66 integers from 00000600000_{6} to 55555655555_{6} in numerical order. If one number can be obtained from another by a rearrangement of digits, then the numbers are congruent modulo 55 (this holds because a number aabcde6=64a+63b+62c+6d+ea^{a b c d e_{6}} = 6^{4} \cdot a + 6^{3} \cdot b + 6^{2} \cdot c + 6 \cdot d + e is congruent modulo 55 to a+b+c+d+ea + b + c + d + e), but if there are 100100 other numbers between them, then their difference is 101101, which is not divisible by 55. So there are no such pairs.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.