Math Question, not for HW

Factual Questions
21

thanks guys (factorial)

22

Got another one. These are practice mathcounts question that a friend’s daughter of mine is trying and when he doesn’t get it, he forwards it to me, and I am now forwarding to this forum.

The digits 1-9 are each used once to form a positive 9-digit integer. There are 362880 possible integers like this. How many of them have the digits 1, 2, and 3 in order from least to greatest throughout the integer? One such example is 451,728,936

(so the 1-2-3 doesn’t have to go in order.)

23

You just need to figure out how many items are in the following list:

123…
12.3…
12…3…
.
.
.
1…2…3.
1…2…3
1…23…
.
.
.
.
…1…23
…123.
…12.3
…1.23
…123

No time now to count it up but I imagine conceptualizing the problem that way should make the math more obvious.

24

nvm

25

Ok, I wrote all the numbers down on a piece of paper, then used 3 different colored highlighters for the digits 1, 2, and 3, with the colors red, green, and blue. Then I counted up the ones that an RGB pattern in them and got 60480. I may not have done this carefully, so I’ll try it again to check.

26

:smiley:

27

Never mind what I posted above: I completely misread the problem.

28

Yep, recounted, 60480 is it.

29

Here’s how to work that problem in a more formal way.

There are 9 “positions”. There are C(9,3) = 84 ways to choose which positions the 1, 2, 3 go in.

This is the simple way to compute what Frylock was trying to do by hand.

*Note: equivalently, you can choose which positions the other 6 numbers go in, or C(9,6) = 84, which works out to the same.

For the other 6 numbers, there are 6! = 720 permutations. For example, if the first three numbers are 123, there are 720 ways to arrange the remaining 6 numbers:

123456789
123456798
123987654
etc

So, there are a total of C(9,3)6! = 84720 = 60,480 such integers, which matches what TriPolar got by hand.

30

To correct the above, you take the number of items on the implied list I gave, and multiply it by the number of possible combinations of six digits in six spaces.

31

doesn’t 9C3 method just give the exact combinations where 1-2-3 are in a row?

32

I don’t know, but he got the same total I did, which included all that had the sequence 1-2-3 going left to right, including numbers like 516283794.

ETA: I assumed you weren’t counting rotations like 345678912.

33

Here’s another way to get the same answer:

Let us call this set of 9-digit integers with the digits 1-9 used once, the set X.

Ignoring all other digits, there’s nothing special about the digits 1, 2, and 3 being in ascending order. They could just as easily be in the order 1, 3, and 2, or 2, 1, and 3.

We can imagine dividing this set X into:
{The subset with 1,2,3 being in the order 123}
{The subset with 1,2,3 being in the order 132}
{The subset with 1,2,3 being in the order 213}
{The subset with 1,2,3 being in the order 231}
{The subset with 1,2,3 being in the order 312}
{The subset with 1,2,3 being in the order 321}

One may check that each number in X belongs to exactly one of these subsets.

Given no further restrictions, one may conclude that by symmetry, these sets are of equal size. The problem statement gives the size of X as 362880, so there are 362880/3! = 60480 such numbers having the digits 1, 2, and 3 in order.

34

No, it’s the number of different positions you can choose for the numbers.

Let’s say you have 9 “positions”

How many ways can you choose 3 of these positions for 1-2-3? The answer is 9C3.

You can always verify it by counting them by hand:

1 2 3 _ _ _ _ _ _
1 _ 2 3 _ _ _ _ _
1 _ _ 2 3 _ _ _ _
etc

There are 9C3 = 84 of these.

As I noted, you can equivalently use 9C6, which is the number of ways of choosing which positions 1-2-3 are NOT in.

After you have that, 6! is the number of combinations for the rest, i.e. after the positions of 1-2-3 are decided.

For example, if you have _ _ 1 _ 2 _ _ 3 _, then there are 6! = 720 ways to arrange the other 6 digits in the blanks.

35

By the way, another way to check the 9C3 is ok is by allowing permutations of 1-2-3.

So, if you allowed 3-2-1, 1-2-3, 1-3-2, etc, we’d have 9P3, instead.

Including the other 6 digits, the total number of integers would be:

9P3 * 6!, which works out to (9!/6!)*6! = 9!

So, the calculation using 9C3 is consistent with allowing permutations of all 9 digits without constraint.

This is the same thing that jpei noted but from the other direction.

36

Ok, so if you want to count rotations, I just looked for all combinations of RGB, BRG, and GBR. There are 181440 of those.

I just realized I didn’t have write down ALL the numbers, just the integers between 123456789 and 987654321. It was really hard writing down those irrational numbers, and you don’t even use them.

37

Props to jpei (I did it the longer way) - that’s very elegant and exactly the sort of thing MathCounts would applaud.

38

Yes, look at that! 3*60480=181440. That would have been way easier.

39

Twofer:

  1. What is the largest value of n for which 213! is divisible by (7!)^n

  2. Let N be any 3-digit integer which has none of its digits equal to zero. Let M be the 3-digit integer formed by reversing the order of N’s digits. What is the greatest integer that is always a factor of the positive difference of N and M. (is it 0?)

40

Since 7 is the largest prime number from 1 to 7. Count all the factors of 7 from 1 to 213 for the answer:
Answer = 213/7 + 213/49 = 34