3

Given set $S$ that contains all numbers of base 3 that share the following characteristics:

  • every element in $S$ share the same number of digits, $x$
  • every element in $S$ can have leading zeros

We aim to solve the optimization problem

$$\max\{x\geq 2 \mid \exists \{n_1,\ldots,n_6\}\subset S: i\neq j \implies n_i, n_j \text{ have at most one coincidence}\}$$

(Coincidence can be defined as a number of duplicate number in the same digit. 2010 and 1220, for instance, has a coincidence of one.)

I manually listed out the elements while increasing $x$ by 1, but soon realized that this is getting too tedious. I proved by trial and error that when $x=4$, the conditions holds as $S=\{0120, 1200, 2010, 0001, 1111, 2221\}$ works. I also suspect that when $x=5$, the conditions does not hold (also done by trial and error), but I'd like to know if there is a mathematical way to confirm that.

I originally planned on using the Pigeonhole Principle, but am quite unsure as to how to utilize it for the proof. Any insight is appreciated.

Good Boy
  • 2,210
jstaxlin
  • 155

1 Answers1

1

In $5$ digits, you can find a set of size 6 with the coincidence property:

$$\{00011, 01102, 10120, 12212, 21221, 22000\}.$$

In $6$ the best you can do is size 4: e.g.,

$$\{000111,011022,102202,220000\}.$$

Claim: $x = 5$

We'll show that a set of size four is the best you can do with six digits.

One can appeal to symmetry to simplify the situation: The coincidence between two numbers is not affected if you

  • reorder the digits (of both numbers in the same way), or
  • apply some bijection of $\{1,2,3\}$ to one of the digits (to both numbers simultaneously).

(E.g., the coincidence of 112 and 110 is the same as 211 and 011, and is the same as 111 and 211.)

Let $S$ denote a set of 6-digit numbers who pairwise share at most one digit.

Without loss of generality, applying symmetries to each of the numbers of $S$ you can assume that one of your numbers in $S$ is $0^6 := 000000$, and the other is

  • $01^5 := 011111$, or
  • $\phantom0 1^6:=111111$,

and we have two cases depending on this second value.

Case 1: $1^6$

If $m,n \in S$ share at most one digit with $0^6$ and $1^6$, then $m,n$ can have at most one $0$-digit and one $1$-digit, and hence each have at least four $2$-digits . But then $m$ and $n$ share at least two $2$-digits (pidgeonhole!), so must be equal.

I.e., if $S$ contains two numbers which have coincidence $0$, $S$ has cardinality at most 3.

Case 2: $01^5$

(This is the first rigorous treatment of this case I could find. Brute force is probably easier from this point!)

In this harder case, if $m, n, p \in S$ share at most $1$ digit with $0^6$ and $01^5$, they each contain at most one $0$-digit and two $1$-digits, i.e., at least three $2$-digits.

Moreover, to avoid the result of the the last case, at least two of these numbers $m$ and $n$ say, must have exactly three $2$-digits, which implies that their first digit must be a $0$ or a $1$, and the three $2$-digits lie in the other five places.

Some pigeonhole principle style thinking says: these $2$-digits for $m$ and $n$ must collectively occupy all five of these spaces, or else they would agree in two or more places.

If they do occupy all five slots, whether or not $p$ has three $2$-digits or more, we find that at least three of these have to be allocated to the same five spaces, and there is no way to avoid agreeing with $m$ or $p$ in fewer than two digits (pigeonhole principle on two slots: those occupied by $m$, and those occupied by $n$ or both.)

That is to say, at least some of the $m,n,p$ coincide in at least two places and are equal. That is, $S$ cannot contain more than four elements.

Good Boy
  • 2,210