Find the 10 digit number, the beautiful math puzzle by Conway
Find the 10 digit number with each digit different and each number formed by first n digits divisible by n. Step by step solution by basic math explained.
To find such a 10 digit number from 3265920 possible 10 digit numbers is not easy, but is not too difficult also. It needs systematic approach.
You may explore more about this 10 digit number puzzle and the creator John Horton Conway, the legendary playful genius of a mathematician with the fortunate streak of bringing fun into math that can literally be enjoyed by all.
In our solution we have used math concepts at the middle school level, but we have also used Problem Solving Techniques and Mathematical reasoning.
Unless approached systematically, the puzzle may be found hard to solve, though practically anyone can solve this puzzle by systematic pattern finding reasoning.
It can be a rich source of learning in middle schools on how to form gradually growing restrictive patterns by basic divisibility rules for 0, 2, 3, 4, 5, 6, 8 and 9 and reasoning.
The 10 digit number puzzle of Conway
Find the 10 digit number, abcdefghij. Each of the digits is different, and,
a is divisible by 1
ab is divisible by 2
abc is divisible by 3
abcd is divisible by 4
abcde is divisible by 5
abcdef is divisible by 6
abcdefg is divisible by 7
abcdefgh is divisible by 8
abcdefghi is divisible by 9
abcdefghij is divisible by 10.
Clarification: Each of the 10 numbers such as abcdefgh is not a product of the digits, it is a number formed by appending the digits one after the other from left to right.
Try to solve the puzzle. And take your time to solve before seeing the solution.
Being a classic math puzzle, there can be other ways to arrive at the solution. Our solution should be among the simplest as far as math used is concerned.
If you try to solve the puzzle, you would enjoy the solution more.
Solution to the 10 digit number puzzle of Conway
How would you approach solving the puzzle?
Would you try out combinations of 10 digits for each place starting from left, test the divisibility for the place and move ahead without deeper analysis and using any faster systematic method?
You may move straight to the solution and skip the following section on the brute-force approach.
An idea on the brute-force approach to solution of 10 digit number puzzle by Conway
As an example, first two digits may be—12,14,16, 18 or 10 for the two digit number formed to be divisible by 2 (or an even number).
And for each of these combinations say 12, possible 3 digit numbers would be—123, 125, 127 or 129—a total of 20 possible combinations.
Now if you test each of the 20 possibilities to see whether it is divisible by 3, a number of these will be eliminated. For example, out of the 4 possibilities for 12 as first two digits, only 123 and 129 will be valid—the other two being not divisible by 3.
Finally, the valid 3 digit numbers you may identify to be 123, 129, 147, 165, 183, 189 and 105, rest being not divisible by 3.
Then you would append the fourth digit, form all possible unique 4 digit numbers and test each to see whether it is divisible by 4.
It is a very tiring and time consuming process, and possibility is high that you would make a mistake on the long road to the solution.
Solution to the 10 digit number puzzle Stage 0: Fixing digits at 5th and 10th places by Divisibility rules
Easier approach adopted,
Identify restrictions on the 9 digits for occupying the 10 places based on the most basic number system rules of divisibility.
First we'll take the simplest decision.
Use divisibility rule of a 10 digit number for 10, the simplest.
The simple rule for any number to be divisible by 10 is its unit's digit must be 0.
Conclusion 1:The 10th digit (or the unit digit) of the final 10 digit number must be 0.
Use divisibility rule of a 5 digit number for 5, the next simplest.
Again it is a simple rule—the unit digit must be 0 or 5.
Conclusion 2: As 0 is already used up in 10th place, the 5th digit of the final 10 digit number can only be 5(as each digit can be used only once and 5 cannot be used for unit digit).
Is this enough at this early stage?
No it's not. Identify with certainty that,
Conclusion 3: The 1st place condition of divisibility by 1 does not mean that the first digit will be 1—it can be any of the remaining 8 digits—1, 2, 3, 4, 6, 7, 8 or 9.
This is an important key pattern to identify.
This is a common mistake one might commit and never find the solution as a result.
Use divisibility rule of a 9 digit number for 9 to understand the nature of the first 9 digits of the solution partly.
If the integer sum or sum of the digits of any number is divisible by 9, it will always be divisible by 9.
Conclusion 4: As the first 9 digits of the 10 unique digit solution contains all the 9 digits from 1 to 9, the sum of the digits is 45 (multiply average 5 by 9). The integer sum 45 being divisible by 9, any combination of digits 1 to 9 in first 9 places would be divisible by 9.
Next conclusion that follows is a bit more complex,
Conclusion 5: No need to test the first 9 digits for divisibility for 9 at all—it will automatically be divisible by 9.
Need to concentrate only on forming the first 8 digits correctly out of which 5 at 5th place is already fixed. The last digit left will take the 9th place taken from left.
The 10 digit number puzzle is to some extent simplified to the task of deciding correct digits for 7 out of first 8 places.
Let's now go over to the next stage to list out the remaining divisibility rules that will be use along with mathematical reasoning to,
Task: Form patterns that create restriction on occupancy of the remaining 8 places (with 0 is at 10th place and 5 at 5th place).
Solution to the 10 digit number puzzle Stage 1: Use Divisibility rules for 2, 3, 4, 6, 8 to discover patterns that create restrictions for remaining 8 places
Divisibility rule for 7 is cumbersome. So it will not be used for identifying restrictive condition with ease. Speed of solution is our goal. Right?
Known result: It is already known that first place can be occupied by any of remaining digits—no restrictions on this place to help us.
Before using any divisibility rule let's form the first obvious pattern of even and odd place occupancy.
Important Pattern 1:
Conclusion 6: Only 2, 4, 6 or 8 can occupy the 2nd, 4th, 6th and 8th or even places. So 1, 3, 7 or 9 can occupy only 1st, 3rd, 7th or 9th odd places.
Reason: This follows from the puzzle condition that, 2, 4, 6 and 8 digit numbers formed by digits taken from left are to be divisible by 2, 4, 6 and 8 respectively. The second part of the Conclusion 6 automatically follows.
Conclusion 7: No two consecutive places can be occupied either by two even digits or by two odd digits.
Let's take up the rest of the divisibility rules.
Divisibility rule for 2—
Any number must have its unit digit as an even digit to be divisible by 2.
No new conclusion can be made by this rule. By Conclusion 6, divisibility of 2 is ensured for the two digit number extracted out of the 10 digit number solution.
Divisibility rule for 3—
Any number must have its integer sum or sum of digits divisible by 3 for the number to be divisible by 3.
Time is not yet right for using this rule. It will be used at the opportune time.
Divisibility rule for 4—
For any number to be divisible by 4, the number formed by its last two digits (from left to right) must be divisible by 4.
It means for our puzzle,
Conclusion 9: Important pattern 1: The number formed by 3rd and 4th place digits together must be divisible by 4. Only possible combinations are—12, 16, 32, 36, 72, 76, 92, 96.
This enumeration of feasible combinations of 3rd and 4th place digits are made by the facts,
- No two consecutive places can have enen digits.
- 5 is already used in 5th place and so can't be used in 3rd place.
- Only 1, 3, 7 and 9 can be placed in 3rd place.
- Numbers 14, 18, 34, 38, 74, 78, 94 and 98 are not divisible by 4.
Look at these 8 two digit numbers once more to discover the important pattern,
Conclusion 10: Important pattern 2: Only 2 or 6 occupy the 4th place.
This is a really important pattern and is discovered just from the available possibilities in the previous pattern, and not using any knowledge on any topic. This pattern, naturally is more restrictive, more abstract and hence more powerful. In fact discovery and use of this type patterns only lead you to a clean and quick solution of a complex problem.
Divisibility rule for 6—
For a number to be divisible by 6, its unit digit must be even and its sum of digits must be divisible by 3.
Conclusion 11: Important pattern 3:
The number formed by first 6 digits of the 10 digit number solution,
Number formed by first three digits must already be divisible by 3.
Pattern 3: And also, the number formed by the next three 4th, 5th and 6th digits must be divisible by 3, that is, their integer sum must be divisible by 3 (6th place already ensured to have an even digit).
The last divisibility rule to use at this stage is for 8.
Divisibility rule for 8—
For a number to be divisible by 8, the number formed by its last three digits (from left to right) must be divisible by 8.
This divisibility rule for 8 is by far the most important rule. Using this rule we'll discover and create more and more restrictive patterns step by step.
Conclusion 12: Important Pattern 4:
As 6th place can be occupied by only 2, 4, 6 or 8, and 200, 400, 600 and 800 being divisible by 8, it can further be concluded that,
Number formed by 7th and 8th place digits must be divisible by 8. Only possible combinations are—16, 32, 72 and 96—only 4 possibilities.
Reason: Out of already identified two digit combinations 12, 16, 32, 36, 72, 76, 92, 96 that are divisible by 4: 12, 36, 76, 92 are not divisible by 8 leaving 16, 32, 72 and 96 only.
It further follows from these four possibilities—
Conclusion 13: 8th place can only be occupied by 2 or 6.
Important pattern 5:
Combine pattern 2 and pattern 4 to conclude—
Conclusion 14: Pattern 5: 4th and 8th places can be occupied by only 2 or 6. If 4th place is occupied by 2, 8th place can only have 6 and vice versa.
Till now this is the most valuable pattern discovered. It created what we call (in our Sudoku solution terms), a Cycle in which only two digits can occupy two places. The two places are blocked by the Cycle, and no other digit can occupy these two places or these two digits cannot occupy any other place. This always has a very valuable contribution towards solving complex place occupancy puzzles.
Important pattern 6:
Combine pattern 1 (only 2, 4, 6 or 8 can occupy 2nd, 4th, 6th or 8th places) and pattern 5 (only 2 or 6 can occupy 4th and 8th places), conclude—
Conclusion 15: Pattern 6: 2nd and 6th places can only be occupied by 4 or 8. If 2nd place is occupied by 4, 6th place must have 8 and vice versa. A second Cycle is created fixing four digits within 4 places.
This is the pattern that blocks two more cells for digit occupancy by two more digits. Effectively, Pattern 5 and Pattern 6 together block four places for occupancy by four digits and by no other digits. We have two Cycles and now we can say we have reached the stage where it would be possible to collect all the pattern restrictions together.
Now we are ready to collect all the restrictive information of the six patterns and represent them in an easy to use form.
Solution to 10 digit number puzzle Stage 2: Collection and Representation of key information in a suitable tabular form
All the restrictive conditions in the six important patterns will now be collected in a simple tabular form. The column headings are the place numbers in the 10 digit number solution, and the compound rows hold the possible digits that can occupy the positions.
Collection and representation of key information in a suitable simple tabular form is an important technique in solving many mathematical and logical puzzles.
Solution to 10 digit number puzzle Stage 3: Discovery of new patterns and Systematic enumeration of possible combinations
The next 7th important pattern is discovered using pattern 3. For ease of understanding let's repeat pattern 3,
Conclusion 11: Pattern 3: The number formed by 4th, 5th and 6th digits must be divisible by 3, that is, their integer sum must be divisible by 3.
Using the place restrictions in the table and the pattern 3 restriction identiify the 7th pattern.
Important pattern 7:
Conclusion 16: Pattern 7: The only valid 4th-5th-6th place possibilities are—258 and 654 (254 and 658 are not divisible by 3).
Combine these two feasible possibilities for 4th-5th-6th places with 7th-8th place restrictions in the table to create pattern 8.
Conclusion 17: Important pattern 8:
The only valid 4th-5th-6th-7th-8th place possibilities are—25816, 25896, 65432, 65472.
This is the time to apply divisibility rule for 3 on the first 3 places and form all possible 3 digit valid combinations for first 3 places.
Conclusion 18: Important pattern 9:
The only digit combinations valid for 1st three places till this point of analysis are—147, 183, 189, 381, 387, 741, 783, 789, 981, 987.
Rest of the digit combinations of 1st three places from the table are not divisible by 3 (integer sum not divisible by 3, check for yourself again).
Now combine each of the four valid possibilities for 4th to 8th places—25816, 25896, 65432, 65472 one by one, with the set of 10 valid possibilities for 1st three places. While combining, look for all digit overlaps (or duplication) between the two and eliminate the possibilities with digit duplication as invalid.
It is easier to take each of the members of the smaller (in number of members) set one by one and do the digit overlap test with the whole of larger second set, rather than the other way round. This is an example of problem solving method or technique that we call—smaller to larger set interaction technique.
This gives us the penultimate last but one result.
In the process the ninth digit is also placed.
Critical pattern 10:
Combine 25816—all 8 three digit combinations listed under pattern 9 have one or more than one digit overlaps with 25816.
Combine 25896—valid combinations are: 147258963 and741258963 are the only 2 valid 9 digit combinations. Rest are with digit overlaps.
Combine 65432—valid combinations are: 189654327, 789654321, 981654327, 987654321. Rest have digit overlaps.
Combine 65472—valid combinations are: 183654729, 189654723, 381654729, 981654723. Rest have digit overlaps.
Solution final stage: Test for divisibility of 7
These are the only 10 possible valid 9 digit numbers satisfying divisibility conditions for all places excluding 7th.
Applying divisibility rules, mathematical reasoning, pattern discoveries step by step and combining the patterns of possibilities by systematic enumeration, result obtained is this exhaustive set of valid 9 digit numbers with 7th place test yet to be done.
Only one step is left for getting the final solution—divide each of these 10 possible 9 digit numbers by 7 to see whether it indeed is divisible by 7.
Final result obtained—
Only 381654729 is divisible by 7 and so 3816547290 is the ten digit number satisfying divisibility condition for each of the ten places.
The results of this last action is shown in the table.
The answer to the puzzle question: 3816547290.
This is the only such number possible.
Concepts used are the basic ones for divisibility by 2, 3, 4, 5, 6, 8, 9 and 10 taught in middle schools.
Divisibility by 7 is tested at the last by direct division of a limited possible set of 9 digit numbers by 7 as a Strategy.
Strategically, more stringent and result-bearing (in terms of place restrictions for digit occupancy) divisibility rules for 8 and 4 along with other rules for divisibility of 2, 5, 9 and 10 are used with mathematical reasoning for creating refined restriction patterns for chunks of places.
As a useful technique, collection of restrictions formed in patterns in a simple table for systematic enumeration of larger length valid digit combinations, applying the pattern derived out of divisibility for 6 and mathematical reasoning.
Because of applying more stringent restrictions earlier, the number of valid combinations is limited to only 4.
In the last but second step only the larger set of 10 possible 1st three place combinations are enumerated using validity test for 3. As this test is less restrictive, its use resulted in larger set of possible combinations. That is the reason this step is executed as late as possible as a strategy.
And in the penultimate last but one step, the 4 member smaller set of 4th to 8th place valid digit combinations is combined with the larger set of 10 possible valid combinations for 1st three places.
The process of combining and looking for digit overlaps can be done quickly and easily because of the use of smaller to larger set comparison technique.
In the last step, the set of all possible 9 digit numbers excluding 7th place validity are directly divided by 7 and only 1 of the combinations is found to be divisible by 7.
The systematic method ensured that the only possible solution satisfying all puzzle conditions is found. This property we call as exhaustivity which is inherent in the process.
Though the mathematical concepts needed to solve the puzzle are very basic, the puzzle is large and complex—it needs careful strategizing and applying problem solving techniques to solve it cleanly and quickly.
Creation of patterns and applying suitable methods lie at the heart of systematic solution of the puzzle.
Finally, it should prove to be very useful in teaching middle school students anywhere on—
How such basic concepts can be used so effectively, and of course how to apply problem solving strategies, create or discover powerful patterns, and apply problem solving techniques.
Author's note on 25th February, 2021
After finishing my update of the solution to this beautifully perfect puzzle, when searching for a suitable page to link on John Horton Conway, with great sorrow I find that he passed away on 11th April last year. I mourn for him. Playful geniuses are rare.
Puzzles you may enjoy
10 digit Conway number puzzle with solution