# 6 digit numbers which are multiples of 9 problem

#### apple2357

##### Full Member
I am working on a problem with my 11 year old and we are stuck...

A 6 digit number is made of 1,2,3 only. How many of these are multiples of 9.

We established the biggest number you can make (333333) is a multiple of 9 ( digits add up to 18). So any others will have to be <18 ( i.e. 9).
So other cases are

111222
&
111123

I am struggling to explain how many different permutations of these they are, without resorting to formulae?

#### Subhotosh Khan

##### Super Moderator
Staff member
I am working on a problem with my 11 year old and we are stuck...

A 6 digit number is made of 1,2,3 only. How many of these are multiples of 9.

We established the biggest number you can make (333333) is a multiple of 9 ( digits add up to 18). So any others will have to be <18 ( i.e. 9).
So other cases are

111222
&
111123

I am struggling to explain how many different permutations of these they are, without resorting to formulae?
So you want to make an exhaustive search and list? Why?

That will exhaust you! Use the formulae to have a guess at the size of the list. Then you may choose to exhaust yourself.

#### pka

##### Elite Member
A 6 digit number is made of 1,2,3 only. How many of these are multiples of 9.
We established the biggest number you can make (333333) is a multiple of 9 ( digits add up to 18). So any others will have to be <18 ( i.e. 9).
So other cases are 111222 & 111123
The string $$111222$$ can be arranged in $$\dfrac{6!}{(3!)^2}=20$$ ways.
The string $$111123$$ can be arranged in $$\dfrac{6!}{(4!)}=30$$ ways.
Can you all find others?

#### apple2357

##### Full Member
So you want to make an exhaustive search and list? Why?

That will exhaust you! Use the formulae to have a guess at the size of the list. Then you may choose to exhaust yourself.
More i didn't want to jump to the formulae without trying to explain why.. But i see your point.

#### Jomo

##### Elite Member
You need the formula so that you know how many there will be so that you do not exclude any. There is no need to explain the formula to your child.

#### apple2357

##### Full Member
So can i say 111123 has 30 ways because there are 6 ways of placing the 3 and 5 ways of placing the 2 and the remaining 1111 doesn't matter?
A bit harder with the 111222 though...? Any thoughts

#### Jomo

##### Elite Member
OK, here you go.

For 111222:

Start off with 11. Then you need to permute 1222 which is easy as you just need to put the lone 1 in all 4 positions. This gives you 111222 112122 112212 ans 112221

Now you could also start off with 12. Now you have to permute 1122. Now start of with 11 and get 1122 (121122). Now start of with 12 and get 1212 (121212). Now start off with 21 and then with 22.

Now the first two could have been 21. ....
The 1st two could be 22. .....

There is your method without using formulas!

#### pka

##### Elite Member
So can i say 111123 has 30 ways because there are 6 ways of placing the 3 and 5 ways of placing the 2 and the remaining 1111 doesn't matter?A bit harder with the 111222 though...? Any thoughts
The example in almost all counting books is, $$MISSISSIPPI$$
The number of ways to rearrange that word is $$\dfrac{11!}{4!\cdot 4!\cdot 2!}$$ because of four S's, four I's & two P's.
If we had $$S_1,S_2,S_3,S_4$$ that is four different letters which can be rearranged in $$4!=24$$ different ways.
So removing the subscripts means we have twenty-four identical strings.

So how many can the string $$122333444455555$$ be rearranged?

#### apple2357

##### Full Member
The example in almost all counting books is, $$MISSISSIPPI$$
The number of ways to rearrange that word is $$\dfrac{11!}{4!\cdot 4!\cdot 2!}$$ because of four S's, four I's & two P's.
If we had $$S_1,S_2,S_3,S_4$$ that is four different letters which can be rearranged in $$4!=24$$ different ways.
So removing the subscripts means we have twenty-four identical strings.

So how many can the string $$122333444455555$$ be rearranged?
Yep so (15!)/( 2!3!4!5!)

#### JeffM

##### Elite Member
We can express the numbers that we are interested in terms of two three-digit integers x and y such that

$$\displaystyle \dfrac{1000x + y}{9} = \dfrac{999x + x + y}{9} = 111x + \dfrac{x + y}{9}.$$

x and y have a sum divisible by 9 and can be expressed in decimal notation using only the digits 1, 2, and 3.

$$\displaystyle \text {Define } z = x + y. = 100a + 10b + c.$$

a = 2, 3, 4, 5, 6
b = 2, 3, 4, 5, 6
c = 2, 3, 4, 5, 6

Thus there are 125 possible values for z. 221 < z < 667

But we do not need to look at all of them; only those divisible by 9.

From 200 through 699, there are 50 groups of 10 consecutive integers. However, we can exclude groups that have a zero, one, seven, eight or nine as the second digit. That reduces the number of relevant groups to 25. Moreover, we can exclude any group that has two multiples of 9 because those two multiples must end in 0 and 9 respectively. Those groups are 270-279, 360-369, 450-459, 540-549, and 630-639. In addition the two groups immediately following will have numbers divisible by 9 that end in 8 and 7. We must beware of double counting here because many of these groups have previously been excluded. What have not yet been excluded are 460-469, 550-559, 560-569, 640-649, and 650-669. Furthermore, we must exclude the group immediately preceding a group with two numbers divisible by 9 because that preceding group will have a number divisible by 9 that ends in 1. that is another 5 groups. All told we are down to just 10 groups, namely

220-229, 230-239, 240-259, 320-329, 330-339, 340-349, 420-429, 430-439, 520-529, and 660-669.

Moreover, the numbers that are divisible by 9 follow a simple pattern.

225, 234, 243, 324, 333, 342, 423, 432, 522, and 666.

I am getting too tired to finish this tonight. It's a bit tedious. I have no idea why an 11 year old was assigned this. But I do think the way to attack this is more number theoretic rather than combinatorics.

Couple of thoughts. Some of these sums can be achieved in only one way.

333 + 333 = 666 This leads to only one permitted six-digit number.

Others can be achieved in two ways. For example,

112 + 113 = 225 = 113 + 112. That has to be counted as two ways because we must assign the numbers to x and y. So the sum
225 corresponds 112113 and 113112. I am too sleepy to think any more, but sums that contain the digit 4 in any position are going to create more than a single pair of numbers. I suspect a bit of care is needed in this last part,

#### JeffM

##### Elite Member
There is a mistake in my previous post.

There are 50 groups of 10 consecutive integers ranging from 200 through 699. We can exclude the 25 groups that have the forms a0b, a1b, a7b, a8b, and a9b. That leaves 25 groups. We can also exclude the five groups that have two multiples of 9 because those multiples end in 0 and 9. Those groups start at 270, 360, 450, 540, and 630. But I missed a double counting problem: we already excluded the 270 group. So we subtract 4 from 25, leaving 21 groups.

The next exclusion has a double counting problem that I did not miss. We need to exclude the two groups that follow a group containing two multiples of 9 because the multiples of 9 in those groups have a final digit of 8 or 7. That is 10 groups starting with 280, 290, 370, 380, 460, 470, 550, 560, 640, and 650. However, we previously excluded the groups starting with 280, 290, 370, 380, and 470. So we are only excluding 5, reducing 21 to 16.

Finally, w need to exclude the group that precedes a group containing two multiples of 9 because the multiples of 9 in those groups have a final digit of 1. Obviously, there are five such groups, namely those starting with 260, 350, 440, 530, and 620. There is no double counting issue here. So we are left with 11 groups, namely

220-229, 230-239, 240-249, 250-259, 320-329, 330-339, 340-349, 420-429, 430-439, 520-529, 660-669.

The 11 sums that are divisible by 9 are

225, 234, 243, 252, 324, 333, 342, 423, 432, 522, and 666.

I at first tried to find the different ways to put together pairs of numbers from the allowed set that sum to one of those eleven numbers by hand. It was tedious, and I kept making mistakes. There is sort of a pattern, but it was not obvious to me until I resorted to computer, which is how I found my counting mistake in the first place.

Here are the results.

possibilities for

225 are two, namely 112 + 113, 113 + 112

234 are six, namely 111+123, 112 + 122, 113 + 121, 121 + 113, 122 + 112, 123 + 111

243 are six, namely 111 + 132, 112 + 131, 121 + 122, 122 + 121, 131 + 121, 132 + 111

252 are two, namely 131 + 121, 121 + 131

324 are six, namely 111 + 213, 112 + 212, 113 + 211, 211 + 113, 212 + 112, 213 + 111

333 are eight, namely 111 + 222, 112 + 221, 121+ 212, 122 + 211, 211 + 122, 212 + 121, 221 + 112, 222 + 111

342 are six, namely 111 + 231, 121 + 221, 131 + 211, 211 + 131, 221 + 121, 231 + 111

423 are six, namely 111 + 312, 112 + 311, 211 + 212, 212 + 211, 311 + 112, 312 + 111

432 are six, namely 111 + 321, 121 + 311, 211 + 221, 221 + 211, 311 + 121, 321 + 111

522 are two, namely 311 + 211 , 211 + 311

666 is one, namely 333 + 333

Thus, unless I have made another error, there are exactly 51 six-digit numbers that contain only the digits 1, 2, and 3.

No way a kid of 11 is supposed to solve this unless this is for a programming class.

#### pka

##### Elite Member
No way a kid of 11 is supposed to solve this unless this is for a programming class.
I am working on a problem with my 11 year old and we are stuck...
A 6 digit number is made of 1,2,3 only. How many of these are multiples of 9. We established the biggest number you can make (333333) is a multiple of 9 ( digits add up to 18). So any others will have to be <18 ( i.e. 9). So other cases are 111222 & 111123
So let's be clear, there are just three cases to count.
There is only one way to arrange $$333333$$.
There are twenty ways to arrange $$111222$$.
There are thirty ways to arrange $$111123$$.
That is fifty-one ways to use only the digits $$1,~2,\text{ and/or }3$$ to make six digits numbers that are multiples of nine.

#### apple2357

##### Full Member
I don't think my son was really expected to solve it but it was more an extension problem he was given to think about and discuss with other kids interested in maths over Zoom! So he decided to ask me and I got stuck at the various permutations stage! I think its accessible to a point just before thinking about why there are 20 ways of arranging 111222, the rest he made some progress with.
I did help him by first thinking about 3 digit numbers ( using 1,2,3) which were multiples of 9, then 4 etc

Thanks all.