Nine digit puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
DataGenetics
Posts: 24
Joined: Sat Jan 01, 2011 1:12 am UTC
Location: Seattle

Nine digit puzzle

Postby DataGenetics » Mon Mar 05, 2018 7:42 pm UTC

Not too challenging, and fun to solve over a cup of coffee, if you've not seen it before.

Question:
Arrange the digits 1-9 to make a nine digit number such that the first digit is divisible by one, the first two digits divisible by two, first three digits divisible by three …

Solution here: http://datagenetics.com/blog/march22018/index.html

User avatar
Bloopy
Posts: 212
Joined: Wed May 04, 2011 9:16 am UTC
Location: New Zealand

Re: Nine digit puzzle

Postby Bloopy » Wed Mar 07, 2018 9:05 am UTC

Almost too challenging for me but got it eventually. I used a bit of dumb trial and error.

Spoiler:
381654729

I thought checking for divisibility by 7 would be the snag to rule out a lot of possibilities so I aimed to sort that out much earlier than the linked solution. I put the 5 in place and put 2,4,6,8 in the even positions in any old order. Then I tried the other odd digits in various permutations preserving the divisibility by 3, while using the first method posted here to check for divisibility by 7 (I found it easier to swap digits around in a formula rather than a 7 digit number). If none of those worked, I rearranged the 2,4,6,8. Eventually after a few wrong turns I paid a bit more attention to the divisibility by 4, 6 & 8 and homed in on the answer fairly quickly.

User avatar
patzer
Posts: 429
Joined: Fri Mar 30, 2012 5:48 pm UTC
Contact:

Re: Nine digit puzzle

Postby patzer » Thu Mar 08, 2018 1:30 pm UTC

Solution:

Spoiler:
Unless I'm misunderstanding it, this puzzle seems fairly trivial. Just do it from left to right– there's always a number you can use.

One solution is 444456648.

I'd estimate that there would be approximately 2756 possible solutions to this puzzle ( = 10^9 / 9! ).

Would be much more difficult, of course, with more digits. Try to solve the puzzle with fifteen digits instead of nine!


EDIT: just realized I misread the puzzle. Didn't see the "arrange the digits 1 to 9" bit...
If it looks like a duck, and quacks like a duck, we have at least to consider the possibility that we have a small aquatic bird of the family Anatidae on our hands. –Douglas Adams

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3486
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Nine digit puzzle

Postby Soupspoon » Thu Mar 08, 2018 7:39 pm UTC

Spoiler:
Place the 5 the only place it can go. The four even numbers have only four places, and these in turn tie down the 3, 6, and 7-place numbers (the 1-digit solution is always unconstrained, save by availability, as is the 9-digit one) with some digits already ruled out, through prior use, as you progressively fill in the gaps and check the multiples (when you add digit 3 you can validate 3ness, 4ness and 6ness; if so, adding digit 7 validates/otherwise 7ness and 8ness; 1/2/5/9ness is inherent).

There may be a quicker method, but with a phase-space significantly lower than 1x(4x3x2x1)x(4x3x2x1), as dead-ends reveal themselves and the (sole) solution pops out.

***long pause, before actually posting…***

I actually just tried semi-brute-forcing the answer in various ways, the "intelligent" solution has the program hit 34 dead ends on the way to the answer, while with the most basic method of trying (the current remainder of) digits 1..9 from position 1 to position 9, moving onto the next most recent alternative option at each failure, hits 413 failures along the way with trying the order-of-preference of digits 9..1 giving 2127 failures!

Obviously depends upon order of preference (present the digits in the order of the eventual answer, and it gets there with zero failures) and I'm tempted to meta-brute-force all permutations of 1..9 to see the total range of possibilities (from straight to the answer to the absolute worst 'misteps all the way' combination, which is not necessarily the exact reverse of the answer, as it should also pass muster in lower lengths to waste time) but that'd need another layer of multilayer iteration atop my dumb-and-dumber engines.

(Unintelligently) populating in any order other than left-to-right is already a bad idea, if you need to wait for the first digit to be permuted in before you can yay-or-nay any multiple (besides the 5 and the cut-down selection necessary on the even spots, but I'm not crediting that brute-forcer with any programmed-in sense to do that), so we can probably forget about meta-meta-bruteforcing a more generalised strategy, knowing that it's a total waste.


there's a spoiler tag. use it. -jr
Last edited by jestingrabbit on Mon Apr 02, 2018 5:56 pm UTC, edited 1 time in total.
Reason: to spoiler an answer


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 3 guests