Est. 1998 — 27 years of woodworking knowledge
Friday puzzle -- Three Digits
Find three unique digits such that every permutation of those digits forms a three-digit number (no leading zeros) that is the product of exactly two primes. E.g., 391 = 17*23, and 319 = 11*29, so far so good, but 139 is prime, so 1,3,9 aren't the three digits.
Extra credit for a non-computer, non-brute-force solution.
Thought starter
Digits cannot be 2 or 6 and 4 and 8 would be mutually exclusive. One or the other, but not both. (if either)
Re: Thought starter
sounds like a good systematic approach. Valid deductions so far. a little more available by logic, then it's brute force.
Another
Cannot contain both 7 and 5 or at least one permutation would be divisible by 25. (5*5* some other number)
plus
You can easily show that the number cannot be all odd digits.
Re: plus
From here, brute force. Has either a 4 or an 8 and 2 odd numbers.
How about
178
:-)
Some Counts
Dan nailed this one. But if you are interested, here's how the candidates get whittled down before testing:
Start with C(9,3)= 84 possibilities for the three non-zero digits. (Note on notation: C(N,X) refers to the combinations of N things taken X at a time, = N!/((N-X)!*X!), or 9*8*7/(3*2*1) for C(9,3)
Eliminate 2 and 6, and you are down to C(7,3) = 35 choices
Eliminate all combinations including 4 and 8 or 5 and 7 eliminates 5 combinations each, so down to 25 possibilities, 18 of which have one even digit, and 7 of which are all odd.
We can actually narrow it a little more before brute force, although using brute force at this point gets the answer pretty quickly if you start in the right place!
From the odds, we can eliminate 1,3,5, since the digits add to 9, thus any number using only those digits is a multiple of 9.
From the ones with one even, we can eliminate seven combinations where the sum of digits are a multiple of 3, since those would have two orderings each that are multiples of 6. So instead of having to brute force 84 combinations (504 numbers), we are down to 6 all odd combinations and 11 combinations with one even digit.
I've seen a solution that carries it further, considering the nature of the prime multipliers to get down to only one possibility, but I think at this point, brute force is just as easy.
Dan: You said it was easy to see that all odd combinations didn't work. I agree by testing the ones left, but did you see something else that led you to taht conclusion?