On 2012-04-13 11:15, Arwyn wrote:
> Clever logic should enable you to find the nine-figure number that I
> have in mind. It consists of the digits 1 to 9 in some order, and in
> the number each digit is next to another that differs from it by one.
> In just one case a digit has both neighbours differing from it by one.
> Furthermore, the solution is exactly divisible by more than
> three-quarters of the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12.
> What is the nine-figure number?
Totally off topic.
Did anyone solve this? I made some progress, but didn't nail it.
Lemma 1: The solution must be divisible by 4.
Assume the solution is not divisible by 4. It is therefore not
divisible by 8 or 12. However, this would mean that the solution is
only divisible by at most 3/4th of the numbers between 1 and 12, which
contradicts the problem, which states it is divisible by strictly more
We could apply the same argument to 2 and 3, but we don't need to...
Lemma 2: The solution is divisible by 1, 2, 3, 4, 6, 7, 8, 9, 11 and 12,
but not 5 or 10.
All numbers divisible by 10 end in 0. The solution doesn't contain a
0. We know from Lemma 1 that it's divisible by 4. If it is also
divisible by 5, it must also end in 0. If the solution were not
divisible by any other numbers on the list, it would only be divisible
by 3/4ths, which contradicts the problem, so it must be divisible by the
Lemma 3: The solution must end in 12, 32, 56 or 76
Because the solution is divisible by 4, it's last two digits must be
divisible by 4. The two digits must differ by 1. The second digit must
be even, since it is divisible by 4, so the first digit must be odd.
This only leaves a few possibilities. Checking them, we find that 12,
32, 56 and 76 fit the bill.
Lemma 4: The solution cannot end in 32.
Assume the number ended with 32. According to the rules, the digit 1
must be next to digit 2. However, digit 2 is at the end, so this is a
Ending 12 can be split up 3 ways:
- Containing (34 or 43) and (56 or 65) and (789 or 987)
- Containing (34 or 43) and (567 or 765) and (89 or 98)
- Containing (345 or 543) and (67 or 76) and (89 or 98)
= 3*2*2*2*3*2*1=144 possibilities
Ending 56 can only split 1 way:
- Containing (12 or 21) and (34 or43) and (789 or 987)
= 1*2*2*2*3*2*1=48 possibilities
(Note that, ending 456 is not allowed unless the preceding digit is 3,
because then we'd have to form a group from 123, or leave 3 on it's own)
Ending 76 can be split up 2 ways:
- Containing (12 or 21) and (345 or 543) and (89 or 98)
- Containing (123 or 321) and (45 or 54) and (89 or 98)
= 2*2*2*2*3*2*1= 96 possibilities
Brute forcible, but the question suggests we shouldn't need to.
Can we exclude more possibilities using other divisors?
2: Not really any help, as we already made use of 4, which is strictly
3: No help - if you rearrange the digits of a number divisible by 3, you
get another number divisible by 3. So we can't exclude any wrong
answers, because they will also be divisible by 3.
4: Already used
9: No help for the same reasons as 3.
8 can be used to restrict the 3rd from last digit, but it only excludes
a handful of possibilities (it doesn't even uniquely determine the 3rd
digit). Depending on whether the last 2 digits are divisible by 8, the
second to last digit must be either even or odd. Some possibilities are
excluded because the result in illegal combinations of digits)
My gut feeling tells me that 12 isn't very useful - we already made use
of one it's factors (4) and we know that the other one (3) provides no
useful information, so I don't think 12 tells us anything. (But I'm
not sure I have a watertight argument, so I could be wrong here)
So I'm pretty sure we need to make use of 7 and 11 - but I can't see an
easy way or doing so (without doing a tonne of algebra, which I don't
think the question is looking for)