
4. The set $X$ of $N$ four-digit numbers formed from the digits $1,2,3,4,5,6,7,8$ satisfies the following condition:

for any two different digits from 1, 2, 3, 4, 5, 6, 7, 8 there exists a number in $X$ which contains both of them.

Determine the smallest possible value of $N$.


## Solution

Let some digit, say 1 , appear in exactly $k$ numbers from the $N$ given numbers. Hence, 1 forms at most 3 distinct pairs with the remaining 3 digits of any of these $k$ numbers. Since the total number of all distinct pairs formed by 1 and the other 7 numbers $\{2,3,4,5,6,7,8\}$ is equal to 7 , we see that $3 k \geq 7$. So $k \geq 3$. Therefore, each of the digits $1,2,3,4,5,6,7,8$ must appear in at least 3 numbers. Thus, the total number of all digits in $N$ numbers is at least $8.3=24$. But $N$ numbers contain exactly $4 N$ digits. Therefore, $4 N \geq 24$, so $N \geq 6$. The following example shows that there are 6 four-digit numbers satisfying the problem condition:

1234, 1567, 1268, 2357, 3468, 4578.
