Problem: A certain state issues license plates consisting of six digits (from 0 to 9). The state requires that any two license plates differ in at least two places. (For instance, the numbers 027592 and 020592 cannot both be used.) Determine, with proof, the maximum number of distinct license plates that the state can use.

http://artofproblemsolving.com/community/c1590h1015789s3_problem_6_1990_usamo_1 https://www.artofproblemsolving.com/wiki/index.php?title=1990_USAMO_Problems/Problem_1

There are different ways of assigning plates that result in different maximums. To demonstrate, specialize with simplified 3-digit binary rules. The set of all plates is {000, 001, 010, 011, 100, 101, 110, 111}. We can draw a graph where plates are connected if they differ in one position:

In [22]:
G = nx.Graph()
for i in range(8):
    G.add_node(i)
    [G.add_edge(i,i^k) for k in [1,2,4]]
    
pos = nx.spring_layout(G)

nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, nodelist=range(8), node_color='#C0C0C0', node_size=1100)

labels = {k:bin(k)[2:].rjust(3,'0') for k in range(8)}
nx.draw_networkx_labels(G, pos, labels, font_size=16)

plt.axis('off')
plt.show()

Watch what happens if we issue plates 000 then 111:

In [24]:
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, nodelist=[0,7], node_color='r', node_size=1100)
nx.draw_networkx_nodes(G, pos, nodelist=[1,2,3,4,5,6], node_color='#C0C0C0', node_size=1100)
nx.draw_networkx_labels(G, pos, labels, font_size=16)
plt.axis('off')
plt.show()

You've maxed out assignments to only 2 plates, because they "touch" all other plates, disqualifying them due to differing in only one position.

There are 4 two-plate issues that do this because each of the 8 possible plates is paired with another that is hamming-3 distance away. Or geometrically, there are 4 cases of opposite corners in the hamming cube: (000,111), (110,001), (101,010), (100,011).

The solution to the original problem first established an upper bound, then sought to reach this bound. Anything $\gt10^5$ plates isn't possible. We imagine $10^5$ pigeonholes and insert pigeons (license plates) using their first 5 digits as an index. At $10^5+1$ plates, one hole must have been assigned two plates with the same first 5 digits. This leaves only the 6th digit able to satisfy the 2-digit difference requirement, a possibility.

Next, it aims at this ideal $\gt10^5$ bound: Given that $10^5$ plates can be collected so that any pair differs in at least one position, is it possible to always assign the 6th digit so that at least two digits differ? There are only two cases for pairs of plates selected from the $10^5$:

  • place difference $\geq2 \to$ 6th digit assignment doesnt matter
  • place difference $=1 \to$ 6th digit assignment is critical

The solution assigns the 6th digit as the sum of the previous digits modulo 10. In other words, the sum of the digits of any two numbers that differ in one position will have a one's place that also differs.

Applying this to our toy example, we consider the first two bits as keys into pigeonholes:

hole_0: 00
hole_1: 01
hole_2: 10
hole_3: 11

And assign the third bit as the modulo 2 sum of the previous bits, or its parity:

hole_0: 000
hole_1: 011
hole_2: 101
hole_3: 110

Drawn:

In [25]:
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, nodelist=[0,3,5,6], node_color='r', node_size=1100)
nx.draw_networkx_nodes(G, pos, nodelist=[1,2,4,7], node_color='#C0C0C0', node_size=1100)
nx.draw_networkx_labels(G, pos, labels, font_size=16)
plt.axis('off')
plt.show()