Problem 350

[JMW1994]

I was looking at this problem to do and something about it confuses me. I understand mathematically how you get the GCD and LCM. However, I got stumped at this part:

Let f(G, L, N) be the number of lists of size N with gcd G and lcm L. For example:

f(10, 100, 1) = 91.

How did they get 91 for f(G, L, N)?

[TripleM]

{10},{11},..,{100}. Each of these 91 lists of size 1 has GCD >= 10 and LCM <= 100.

[JMW1994]

{10},{11},..,{100}. Each of these 91 lists of size 1 has GCD >= 10 and LCM <= 100.

So are these numbers {10},{11},...,{100} between GCD and LCM? And what happens to the size as you go higher? Is it like this: {10,10}, {10,11}, ..., {10,100},...,{100,100}? I don't know what size actually does.

[TripleM]

That is all explained pretty clearly in the problem (size is defined in the first line) - I'm not really sure which part of the problem statement you're not understanding.

[JMW1994]

Examples are (2,4,6), (2,6,4), (10,6,15,6), and (11).

(2,4,6) and (2,6,4) have 3, (10,6,15,6) have 4 and (11) has one. Is this what you mean?

[TripleM]

Yes:

A list of size n is a sequence of n natural numbers.

[thundre]

Is it like this: {10,10}, {10,11}, ..., {10,100},...,{100,100}? I don't know what size actually does.

Yes, size is the length of the list. They aren't sets; duplicate entries are allowed, and order matters, so you would count (10,100) and (100,10) as different lists.

gcd(10,11) = 1 and lcm(10,11) = 110, so that list fails both requirements.

[JMW1994]

Yes, size is the length of the list. They aren't sets; duplicate entries are allowed, and order matters, so you would count (10,100) and (100,10) as different lists.

gcd(10,11) = 1 and lcm(10,11) = 110, so that list fails both requirements.

But doesn't it have to fail one of them in order to fail both of them?