3 different non-zero digits are chosen to make 6 different 3-digit numbers, with no digits repeated in any number. Some of the 3-digit numbers, N say, is the average of the other five. Find all possible values of N.
[Math] All possible values of N (3-digit numbers) possible formed by non-zero digits
combinations
Related Solutions
One way is to use Inclusion/Exclusion. You attempted a form of it, but something more elaborate is needed.
You know that there are $\frac{8!}{2!2!2!}$ possible sequences if we have no restriction.
Now let us count the number that have the two $1$'s together. Tie them together, and think of them as a superletter. Now we have $7$ "letters." These can be arranged in $\frac{7!}{2!2!}$ ways. We get the same count for the $2$'s together, and for the $3$'s together. So our first estimate for the required number is $\frac{8!}{2!2!2!}-3\cdot \frac{7!}{2!2!}$.
But we have subtracted too much, for we have subtracted one too many times the patterns that have two $1$'s and two $2$'s together, as well as the ones in which we have two $2$'s and two $3$'s together, and so on. There are $\frac{6!}{2!}$ of each of these, so our next estimate is $\frac{8!}{2!2!2!}-3\cdot \frac{7!}{2!2!}+3\cdot \frac{6!}{2!}$.
But we have added back too much, for we have added back one too many times the $5!$ sequences in which the $1$'s are together, and the $2$'s, and the $3$'s. Our final count is $\frac{8!}{2!2!2!}-3\cdot \frac{7!}{2!2!}+3\cdot \frac{6!}{2!}-5!$.
A start: Here it is easier to count the complementary number: the number of 6 digit positive integers with four or more of one digit repeated.
This reduces to only four cases: (4, 1, 1), (4, 2), (5, 1), (6).
The rest:
(6) is simply $9$. These are $(111111, 222222, \dots, 999999)$.
(5, 1) is a little trickier. First there are $9 * 8$ ways to choose two distinct digits that aren't either zero and assign each to $5$ or $1$. Then there are ${6 \choose 1}$ ways to permute the order.
Now there's case where one is zero. There are $9$ ways to choose the other digit (it can't be zero or else the entire number is zero). For each combination, there are similarly ${6 \choose 1}$ ways to permute the order. In particular, there are ${6 \choose 1}$ ways to permute five zeros and one of the other digit and another ${6 \choose 1}$ ways to permute one zero and five of the other digit. Exactly half of these are valid by symmetry.
Indeed, the bijection that flips each digit demonstrates this property: if we map, e.g., $aaaa0a \mapsto 0000a0$, exactly one of these will be valid for each pair. In this case, we have $a00000, a0aaaa, aa0aaa, aaa0aa, aaaaa0a, aaaaa0$ as valid strings. In total this gives
$$(9 * 8 + 9) * {6 \choose 1} = 486.$$
(4, 2) is similar. There are $9*8$ ways to initially choose and then ${6 \choose 2}$ ways to permute the order.
If one is zero, again there are $9$ ways to choose the other digit and for each combination the number of ways to permute the order is ${6 \choose 2}$. This is
$$(9 * 8 + 9) {6 \choose 2} = 1215.$$
Finally (4, 1, 1). There are $9 * {8 \choose 2}$ ways to choose non-zero digits and assign them to a frequency. There are then $6! / 4!$ permutations. This gives
$$9 * {8 \choose 2} * 6! / 4! = 7560.$$
Now choose a triplet of unique digits $(a, b, c)$ where one is zero. There are ${9 \choose 2}$ ways of doing so. Now, consider the ${6 \choose 4}$ ways to make a string from four $r$'s (r for repeated) and two $s$'s (s for single). If we are given $rsrrrs$, for example, there are now $3!$ ways to choose one of the digits as the repeated and the other two each into one $s$ spot. Of these, two are invalid, namely when we choose the repeated digit to be zero. You can convince yourself this holds for any string. Thus, this gives
$$4{9 \choose 2}{6 \choose 4} = 2160$$
The grand total is $11430$. There are $900000$ six digit numbers in total, so the desired number is $\boxed{888570}$.
Verified solution on computer in Python:
def get_frequencies(cycle):
result = 0
for num in range(10**5, 10**6):
digit_freq = [0]*10
for digit in get_digits(num):
digit_freq[digit] += 1
digit_cycle = sorted([x for x in digit_freq if x != 0], reverse=True)
if digit_cycle == cycle:
result += 1
return result
def get_digits(num):
r = []
while num > 0:
r.append(num % 10)
num /= 10
return r
Running with the following main function:
def main():
print get_frequencies([6], 6)
print get_frequencies([5, 1], 6)
print get_frequencies([4, 2], 6)
print get_frequencies([4, 1, 1], 6)
Outputs the following lines:
9
486
1215
9720
Or, more directly, we can use this program:
def get_frequency_atmost(max_freq, n):
result = 0
for num in range(10**(n-1), 10**n):
digit_freq = [0]*10
for digit in get_digits(num):
digit_freq[digit] += 1
if max(digit_freq) > max_freq:
result += 1
return 10**n - 10**(n-1) - result
which prints $888570$ on input get_frequency_atmost(3, 6).
Best Answer
Rather than go by combination, one may choose to use variables to express the given condition.
Given $a,b,c$ non-zero pairwise distinct, the six numbers that can be formed are $100a+10b+c,100b+10a+c, $etc. (just permute $a,b,c$ in any of six possible orders).
Now, if, for example, $100a+10b+c$ is the average of the other numbers, then five times $100a+10b+c$ is the sum of the other numbers. We know what the other numbers are, so let's write this down: $$ 5(100a+10b+c) = (100b+10a+c)+(100c+10b+a)+(100b+10c+a) + (100c+10a+b)+(100a+10c+b) $$
this simplifies to: $$500a+50b+5c = 212b+122a+221c \implies 378a=162b+216c $$ miraculously, $54$ can be cancelled from both sides of the above equation, and this leaves us with $7a=3b+4c$.
So the question is this:which distinct single digit $a,b,c$ satisfy $7a=3b+4c$?
What helps in our simplification of cases is that transposing in the above equation gives $3(a-b) = 4(c-a)$ (you can expand and check that this is the same as $7a=3b+4c$).
What this means, is that $a-b$ is a multiple of $4$ and $c-a$ is a multiple of $3$. Furthermore, either $c>a>b$ or $b>a>c$ must happen. That is, $a$ is always in the middle.
Now, fix some value for $a$. Find all $b,c$ suitable and check if the equation above is satisfied.
$a=1$ is not possible : it has to be in the middle.
$a=2$ forces either $b$ or $c = 1$, which contradicts the condition we have. Similarly, $a=3$ does not work.
$a=4$ gives $c = 1$ and $b = 8$. So, $481$ is the average of the five other permutes of this number!
$a = 5$ gives $b=9,c=2$ or $b=1,c=8$, so $592,518$ are two other numbers.
$a=6$ gives $b=2,c=9$ so $629$ is another number.
You can check that no other possibilities are there. Interestingly enough, $$ 481 = 37 \times 13 \\ 518 = 37 \times 14 \\ 592 = 37 \times 16 \\ 629 = 37 \times 17 $$
you can try to find why this happens!