p&c q14

S

Saumyojit

Senior Member
Joined
Jan 21, 2020
Messages
1,032
The number of ordered pairs of positive integers (a,b) that can be formed whose lcm is 3^2 * 7^3 * 11 ^4 is


Ordered pair means (a,b) not equal to (b,a) . So i will multiply by 2 for each unique combo.

Power of 3 --> 1,2 ,0
Power of 7 --> 1,2 ,3,0
Power of 11--> 1,2 ,3,4,0

Using bars concept , arranging the bars 1|2 this means that the first number got the factor 3^1 and the 2nd number got the factor 3^2 ...so on

1 2 | --> 3 ways
1,2,3 , | --> 4ways
1,2,3,4, | = 5ways


But in this approach I am missing This type of pair (a,b)-->( 3^0 *7^0 11^4) , (3^2 * 7^3 * 11^3)
 
Saumyojit said:
Using bars concept , arranging the bars 1|2 this means that the first number got the factor 3^1 and the 2nd number got the factor 3^2 ...so on

1 2 | --> 3 ways
1,2,3 , | --> 4ways
1,2,3,4, | = 5ways
Click to expand...
I'm not sure I understand what you are doing; but you recognize that your approach doesn't count everything, so it doesn't matter.

Saumyojit said:
But in this approach I am missing This type of pair (a,b)-->( 3^0 *7^0 11^4) , (3^2 * 7^3 * 11^3)
Click to expand...
It's good that you thought about specific examples; you might want to try a simpler problem (say, only two prime factors with small exponents) and try actually making a list of pairs, in order to get a sense of how it can be done. For example, list the pairs whose LCM is 12.

I can think of a couple possible ways. A key idea is that the exponent of each prime is the larger of the exponents in the two numbers; thinking backward, that means that one number must have the indicated exponent, while the other must be no greater than that. In your example, your second number has 3^2 and 7^3, while the first has 11^4. In each case, the other number has a smaller exponent for that prime (respectively 0, 0, and 3.

So how can you choose exponents for the two numbers?
 
Saumyojit said:
The number of ordered pairs of positive integers (a,b) that can be formed whose lcm is 3^2 * 7^3 * 11 ^4 is
Ordered pair means (a,b) not equal to (b,a) . So i will multiply by 2 for each unique combo.
Power of 3 --> 1,2 ,0
Power of 7 --> 1,2 ,3,0
Power of 11--> 1,2 ,3,4,0
Click to expand...
Good start, so [imath](a,b)=(3^j\cdot 5^k\cdot 11^m~,~3^{2-j}\cdot 5^{3-k}\cdot 11^{4-m})[/imath].
Now what values can [imath]j,~k,~\&~m[/imath] have?
 
Dr.Peterson said:
I'm not sure I understand what you are doing; but you recognize that your approach doesn't count everything, so it doesn't matter.


It's good that you thought about specific examples; you might want to try a simpler problem (say, only two prime factors with small exponents) and try actually making a list of pairs, in order to get a sense of how it can be done. For example, list the pairs whose LCM is 12.

I can think of a couple possible ways. A key idea is that the exponent of each prime is the larger of the exponents in the two numbers; thinking backward, that means that one number must have the indicated exponent, while the other must be no greater than that. In your example, your second number has 3^2 and 7^3, while the first has 11^4. In each case, the other number has a smaller exponent for that prime (respectively 0, 0, and 3.

So how can you choose exponents for the two numbers?
Click to expand...
nothing is coming to my mind
 
Saumyojit said:
nothing is coming to my mind
Click to expand...
When that happens ... try doing something. I suggested one thing to do: Try actually listing pairs whose LCM is 12. This is how I start -- I at least imagine making such a list, and how to organize my thinking; with a lot of experience, that imagination is often enough. For those with less experience, you need to get that experience, by actually doing it.

Show me your list, and tell me how you made sure it would include everything. It will probably not be what I would do, but it will give us something to talk about. And talking about your thinking is the way to learn.

And if you find 12 too hard, try 6 first. That won't catch all the issues you need to think about, but it will be a start.
 
Saumyojit said:
(1,6) , (2,3), (6,6), (6,3), (2,6) are the five pairs that have lcm as 6.
Click to expand...
No, you missed a few. Remember we want ordered pairs. (You can't just count unordered pairs and divide by 2, because some, like (6,6), only have one order.)

But don't forget I said to tell me your thinking, particularly how you know you got everything. The result alone is not enough to learn from; you need to learn to think about your thinking (this is called metacognition), which is necessary to improve your thinking. So we need to talk about that.
 
Dr.Peterson said:
to tell me your thinking
Click to expand...
nothing coming to my mind


pka said:
Good start, so (a,b)=(3j⋅5k⋅11m , 32−j⋅53−k⋅114−m)(a,b)=(3^j\cdot 5^k\cdot 11^m~,~3^{2-j}\cdot 5^{3-k}\cdot 11^{4-m})(a,b)=(3j⋅5k⋅11m , 32−j⋅53−k⋅114−m).
Now what values can j, k, & mj,~k,~\&~mj, k, & m have?
Click to expand...

what is pka method . I gave a thought but cannot simplify
 
Saumyojit said:
nothing coming to my mind

what is pka method . I gave a thought but cannot simplify
Click to expand...
I think pka is talking about how to find pairs whose product is the given number, rather than the LCM.

If you can't think at all, then get some sleep and see if you can dream about it. The goal here is to teach you to solve problems on your own without needing other people as a crutch, so I don't want to say too much about my own ideas.

But I think I've told you something already that you haven't interacted with yet:
Dr.Peterson said:
A key idea is that the exponent of each prime [in the LCM] is the larger of the exponents in the two numbers; thinking backward, that means that one number must have the indicated exponent, while the other must be no greater than that. In your example, your second number has 3^2 and 7^3, while the first has 11^4. In each case, the other number has a smaller exponent for that prime (respectively 0, 0, and 3.

So how can you choose exponents for the two numbers?
Click to expand...
At least tell me if you understand my description of how the LCM works.

Here's an example: For LCM = 12, the factor 2^2 must appear in at least one of the two numbers. (Otherwise, the LCM would have a smaller power of 2.) Suppose it's in the first; how many ways are there to use factors of 2 in the second? Then do similar thinking with 3^1. Then you'll need to think carefully to avoid overcounting.

But again, this is not the only way to do it, and if you allow yourself to think, you may find a better way.
 
Sorry for the typo. Do you understand that [imath]LCM(a,b)=3^2\cdot 7^3\cdot 11^4=45196767~?[/imath]
So if [imath]a=3^1\cdot 7^3\cdot 11^2=124509[/imath] then it must be that [imath]b=363=3^1\cdot 7^0\cdot 11^2~?[/imath]
 
Last edited:
pka said:
Sorry for the typo. Do you understand that [imath]LCM(a,b)=3^2\cdot 7^3\cdot 11^4=45196767~?[/imath]
So if [imath]a=3^1\cdot 7^3\cdot 11^2=124509[/imath] then it must be that [imath]b=363~?[/imath]
Click to expand...
I hate to contradict you, but that's not true. That's what b has to be if their product is 45196767. The problem is about the Least Common Multiple. There are many possible values for b, and 363 is not one of them.
 
Dr.Peterson said:
Here's an example: For LCM = 12, the factor 2^2 must appear in at least one of the two numbers.
Click to expand...
lcm of 2 nos = hcf * co prime factors

lcm= 12 then ,

If i already fix 2^2 as a factor in the first; how many ways are there to use factors of 2 in the second? 3 ways (2^0 ,1,2)
If i already fix 3^1 as a factor in the first; how many ways are there to use factors of 2 in the second? 2 ways (3^0 ,1)

This generates combo which have one number as 12 and others are 1,2,... etc and also (12,12)

And total ordered is 11.

Now I need to find this combo (4,3) , 4,6 ,
Okay so i fix this time 2^2 in first and 3^1 in second ?

So i am fixing the highest factors all in first 1st case and then one in first and second in the second case .
 
Last edited:
Saumyojit said:
lcm of 2 nos = hcf * co prime factors
Click to expand...
This could be the basis of a different method; I'd considered it, but didn't pursue it. It might work out well.

Saumyojit said:
And total ordered is 11.
Click to expand...
How did you get that? And what does it represent?

Saumyojit said:
Now I need to find this combo (4,3) , 4,6 ,
Click to expand...
I don't know what this means.

Saumyojit said:
Okay so i fix this time 2^2 in first and 3^1 in second ?

So i am fixing the highest factors all in first 1st case and then one in first and second in the second case .
Click to expand...
Yes, this idea is a key part of my suggestion. Run with it. And keep going until you have either a way to list or a way to count.
 
Dr.Peterson said:
I hate to contradict you, but that's not true. That's what b has to be if their product is 45196767. The problem is about the Least Common Multiple. There are many possible values for b, and 363 is not one of them.
Click to expand...
Please, never hate correcting a stupid stupid mistake. Thank you. My brain has been elsewhere this entire weekend.
It is now a more involved question than a simple multiplication.
 
Okay I will be fixing each of the highest factor that is present in LCM
So there are three bases 3,7,11.
I have two numbers in every case.

So 3^2 factor can go to one of two places= 2 ways and when it goes to one number then the other number can have power of 3 less than 2 i.e 0,1. So, 2 ways.
2*2=4 ways of placing factor 3 .
Now the second and first can have 3^2 at the same time. So, [2*2 +1]=5 ways.

Similarly for 7^3, [2*3+1] =7 ways

Similarly for 11, 2*4+1=9

315 answer
 
Saumyojit said:
Okay I will be fixing each of the highest factor that is present in LCM
So there are three bases 3,7,11.
I have two numbers in every case.

So 3^2 factor can go to one of two places= 2 ways and when it goes to one number then the other number can have power of 3 less than 2 i.e 0,1. So, 2 ways.
2*2=4 ways of placing factor 3 .
Now the second and first can have 3^2 at the same time. So, [2*2 +1]=5 ways.

Similarly for 7^3, [2*3+1] =7 ways

Similarly for 11, 2*4+1=9

315 answer
Click to expand...

That is the right answer, and very similar to my method. I got it as (2*3-1)(2*4-1)(2*5-1) = 5*7*9 = 315.

So how did you get from having no idea and not wanting to try, to solving it so neatly? (I assume you didn't find a solution online.)
 
Dr.Peterson said:
That is the right answer, and very similar to my method. I got it as (2*3-1)(2*4-1)(2*5-1) = 5*7*9 = 315.

So how did you get from having no idea and not wanting to try, to solving it so neatly? (I assume you didn't find a solution online.)
Click to expand...
You are intelligent enough to catch me .
I gave up and saw solution understood it , then wrote without seeing.



In how many ways can a 12 step staircase be climbed taking 1 step or 2steps at a time ?


Now the approach is
Either 12 single steps --> 12c1=12 .

Or
10 single steps and one two Steps= 12c2= 66

Total 78

where am I wrong?
 
You must log in or register to reply here.
Top