Find the 10 digit number, the beautiful math puzzle by Conway
A few days back from a news item in my stream, I got this beautiful puzzle.
You may explore more about this math puzzle and the creator John Horton Conway, a gifted 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 level of Class 5 or 6, but yes, have to use Problem Solving Techniques and Mathematical reasoning as is our custom for solving math puzzles. The techniques largely are derived from common sense and a bit of experience.
Overall, the puzzle unless approached systematically, may become hard to solve. Otherwise, practically anyone can solve it and this can be a rich source of learning in middle schools.
The 10 digit puzzle of Conway
The following is the puzzle as it appeared.
I have a ten 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
What’s my number?
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.
Try to solve the puzzle. And take your time to solve before seeing the solution.
Following is our solution of the puzzle. But remember: being a classic math puzzle, there can be other, possibly more laborious, ways to arrive at the solution.
More importantly, if you have really tried to solve the puzzle, you would enjoy the solution more.
Solution to the 10 digit puzzle of Conway
Let us mention here, we are averse to deeper mathematics and so we always try to find out solutions based on simpler patterns and methods that would be clear to most people.
Question is—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 skip the following section in which an idea is given on the brute-force approach.
For 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 way.
You realize that a better way to solve must be to first refresh and list out the basic concepts and techniques that must be used for solving the puzzle.
Solution Stage 0: Precise problem definition, fixing digits at 5th and 10th places by Divisibility rules
The very first activity in any problem solving is to define or understand the problem more precisely or accurately.
Divisibility rule of a 10 digit number for 10
The simple rule for any number to be divisible by 10 is its unit's digit must be 0.
In our puzzle that fixes the 10th digit of the final 10 digit number as 0 with certainty.
Divisibility rule of a 5 digit number for 5
Again it is a simple rule—the unit's digits must be 0 or 5.
As 0 is already used up in 10th place, the 5th digit of the final 10 digit number can only be 5.
Is this enough at this early stage?
No it's not. Now only you must realize that,
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 a common mistake one might commit and never find the solution as a result.
And finally, if you consider the 9 digit number of the solution, you would realize that,
All the 9 digits 1 to 9 will be there in any 9 unique digit number formed by 9 digits.
Divisibility rule of a 9 digit number for 9
If the integer sum or sum of the digits of any number is divisible by 9, it will always be divisible by 9.
In our case, 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.
The outcome of this is—you don't have to test the first 9 digits for divisibility for 9 at all—it will automatically be divisible by 9. You would concentrate only on forming the first 8 digits correctly out of which 5 at 5th place is already fixed.
Let's now go over to the next stage to list out the remaining divisibility rules that we would use along with mathematical reasoning to form patterns or restriction on occupancy of the remaining 8 places.
Solution Stage 1: Divisibility rules for 2, 3, 4, 6 and 8 and discovery of preliminary patterns or restrictions on digits occupying the 8 remaining places
We don't know how to use divisibility rule for 7 for the 7 digit part of the 10 digit number that can be used for creating restrictive conditions on 10 places. So at the last stage we would divide each of the possible numbers formed by first 7 digits by 7 directly to test divisibility for 7.
You already know that first place can be occupied by any 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:
Only 2, 4, 6 or 8 can occupy the 2nd, 4th, 6th and 8th or even places and 1, 3, 7 or 9 can occupy 1st, 3rd, 7th or 9th odd places.
No two consecutive places can be occupied either by two even digits or by two odd digits.
First divisibility rule will be for 2.
Divisibility rule for 2—
Any number must have its unit's digit as an even digit to be divisible by 2.
The second place of the 10 digit number can have only the digits—2, 4, 6 or 8.
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.
We would use this rule at the right 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,
The number formed by 3rd and 4th digits together must be divisible by 4. Possible combinations are—12, 16, 32, 36, 72, 76, 92, 96. (as numbers like 14 or 18 are not divisible by 4 and 5 is already used in 5th place and so can't be used in 3rd place).
This number of possibilities 8 being a bit large, we look at these two digit numbers closely and discover the second important pattern,
Important Pattern 2:
Only 2 or 6 can 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's digit must be even and its sum of digits must be divisible by 3.
Important pattern 3:
The first three digits having been already taken care of for divisibility by 3 (assume, as we are looking at 6th place divisibility earlier places assumed to be taken care of), for the number formed by first 6 digits to be divisible by 6,
The number formed by 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 we would 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 build (form or discover) more and more restrictive patterns step by step.
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, we can further conclude that,
Number formed by 7th and 8th place digits must be divisible by 8. Possible combinations are—16, 32, 72 and 96—only 4 possibilities.
It further follows from these four possibilities—
8th place can only be occupied by 2 or 6.
Important pattern 5:
Combining pattern 2 and pattern 4, you can conclude—
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:
Combining pattern 1 (only 2, 4, 6 or 8 can occupy 2nd, 4th, 6th or 8th places) and pattern 5, you can conclude—
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.
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 Stage 2: Collection and Representation of key information in a suitable tabular form
We would represent all the restrictive conditions in the six important patterns in a simple tabular form. The column headings are the place numbers in the 10 digit number, 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 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,
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 you get the 7th pattern.
Important 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 possibilities for 4th-5th-6th places with 7th-8th place restrictions in the table to create pattern 8.
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.
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 and 741258963 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 built-into the process.
Though the mathematical concepts needed to solve the puzzle are very basic, the puzzle is large and complex—it needs careful strategising 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—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.
Puzzles you may enjoy
10 digit Conway number puzzle with solution