Question 26
Each soldier in Illiria’s army has a five-digit code *****. Leading zeros and repeated digits are allowed. Any two soldiers’ codes must differ in at least two positions. We seek the largest possible army.
1. Call the last four digits the “tail”; for example, 12345 has tail 2345. How many different tails are possible?
2. Use the pigeonhole principle: “If n+1 pigeons are put in n boxes, some box contains at least two pigeons.” Compare the possible number of soldiers with the number of tails in part 1.
3. For each different tail, take the units digit of its digit sum as the first digit of the code. For tail 2345, the sum is 2+3+4+5=14, producing code 42345. Prove that any two codes so constructed differ in at least two positions. Count the codes, and hence find the largest possible army.
1. Call the last four digits the “tail”; for example, 12345 has tail 2345. How many different tails are possible?
2. Use the pigeonhole principle: “If n+1 pigeons are put in n boxes, some box contains at least two pigeons.” Compare the possible number of soldiers with the number of tails in part 1.
3. For each different tail, take the units digit of its digit sum as the first digit of the code. For tail 2345, the sum is 2+3+4+5=14, producing code 42345. Prove that any two codes so constructed differ in at least two positions. Count the codes, and hence find the largest possible army.