Arranging Paradox

We consider two cases separately:

Case 1: All four digits are nonzero

In this case, write the digits as $a,b,c,d$ . Then for instance, the digit $a$ is in the thousands place for any of the $3!=6$ permutations of the other digits over the remaining places. Since this is true for for every place, we see that the digit $a$ contributes $6666a$ to the sum of all four-digit numbers made from our four chosen digits. Further, since this is valid for each digit, we find that the sum of all four-digit numbers made from our four chosen digits is $148212 = 6666a + 6666b + 6666c + 6666d \implies a+b+c+d = \frac{148212}{6666} \approx 22.234$ which is impossible since the sum of the digits must be an integer.

Case 2: One of the digits is 0

We use a similar argument, setting $d=0$ . The only difference is that the digit 0 cannot be in the thousands place, so we will find the sum of the four-digit numbers where 0 is in the thousands place and subtract it from our previous computation in the first case. Specifically, if $a$ lies in one of the hundreds, tens, or ones place, then $b,c$ can be placed in the other two places in $2!=2$ ways. Therefore, when 0 lies in the thousands place, $a$ contributes $222a$ to the sum. One again, this argument follows for each nonzero digit, giving a sum of $222a+222b+222c$ which we must subtract from the count we made in the first case: $148212 = 6666a + 6666b + 6666c + 6666(0) - (222a + 222b + 222c) = 6444(a+b+c) \implies a+b+c = \frac{148212}{6444} = 23$ Since $a,b,c$ are distinct digits and $7+8+9 = 24$ we must lower one of $7,8,9$ by one, but the only way to do this and still have distinct digits is to have $\{a,b,c\} = \{7-1,8,9\} = \{6,8,9\}$

From these cases, we can conclude the digits necessarily are $0,6,8,9$ and the smallest four digit number we can make with these is $\boxed{6089}$ .