Suppose we want to build a trinary code for the 26 letters of the alphabet, using strings in which each symbol is 0, 1, or -1.

Question

1. Could we encode all 26 letters using strings of length at most 2?
2. What about using strings of length exactly 3?
3. Compute the maximum number of strings of length exactly 4.
4. Repeat for length exactly 4, but beginning with 0 or 1.

Answer 1

1. Could we encode all 26 letters using strings of length at most 2?

No.

To determine this, we calculate the total number of unique strings available for each length:

1. Length 1: There are 31=331=3 possible strings (0,1,−10,1,−1).
2. Length 2: There are 32=932=9 possible strings (00,01,0(−1),10...00,01,0(−1),10...).

Total unique strings of length 1 or 2 = 3+9=123+9=12.

Since 12 is less than 26, it is impossible to encode the entire alphabet.

2. What about using strings of length exactly 3?

Yes.

1. Length 3: There are 33=2733=27 possible strings.

Since 27 is greater than 26, you have enough unique combinations to encode every letter of the alphabet (with one string left over).

3. Compute the maximum number of strings of length exactly 4.

81.

1. Calculation: 34=3×3×3×3=8134=3×3×3×3=81.

4. Repeat for length exactly 4, but beginning with 0 or 1.

54.

1. First position: 2 options (0 or 1).
2. Second position: 3 options (0, 1, or -1).
3. Third position: 3 options.
4. Fourth position: 3 options.

Calculation: 2×3×3×3=542×3×3×3=54.