To distinguish n objects, we can label them by n binary sequences of length [log2 n] each. Shorter sequences would not do.

How about tristinguishing n objects? In this problem we use ternary sequences for labeling and require that any three of these be different in one and the same coordinate. This is the simplest unsolved case of a problem known as Perfect Hashing. We give a non-existence bound for a similar problem on binary sequences. We also deal with related problems of Edge-Colorings in Graphs. It is shown that the minimum number of tricolorings needed to give every triangle of Kn all the three colors in at least one coloring is at most [log2 n ].

~

KÖRNER, Janos and SIMONYI, Gábor, 1995. Trifference. Studia Scientiarum Mathematicarum Hungarica. 1995. Vol. 30, p. 95–103.