Basic counting methods — integers between 1 and 100 that are divisible by 7

[stunner5000pt]

Homework Statement

Pick two integers between 1 to 100 (inclusive) whose product is divisible by 7. No repetition allowed
Determine the number of numbers that may be formed this way

Relevant Equations

Basic counting methods

There are 14 integers between 1 to 100 that are divisible by 7

If we used indirect approach, then we would do the total number of possibilities C(100,2) = 4,950
and subtract all nubmers that are indivisible by 7 : C(100-14, 2) = C(86,2) = 3,655

the difference of these two numbers is 4,950 - 3,655 = 1,295

Is this the right answer?

Your insight is greatly appreciated!

 

[BvU]

Homework Statement: Pick two integers between 1 to 100 (inclusive) whose product is divisible by 7. No repetition allowed
Relevant Equations: Basic counting methods

Is this the right answer?

Kind of depends on the question -- which you forgot to mention ?

$\$

 

[Mark44]

Homework Statement: Pick two integers between 1 to 100 (inclusive) whose product is divisible by 7. No repetition allowed
Relevant Equations: Basic counting methods

There are 14 integers between 1 to 100 that are divisible by 7

If we used indirect approach, then we would do the total number of possibilities C(100,2) = 4,950

If the product is divisible by 7, then at least one of the numbers must be divisible by 7. As you said, there are 14 integers in the interval [1 ... 100] that are multiples of 7. You don't want C(100, 2) since you're not going to pick just any 2 numbers out of the 100 of them.
The condition that "No repetition allowed" likely means that we shouldn't count 7 * 7, 14 * 14, and so on.

 

[stunner5000pt]

Kind of depends on the question -- which you forgot to mention ?

$\$

Sorry about this. Added that question as well

Further to Mark44's comment, the answer I got still seems to be double counting the 7x7, 14x14, and so on

Is it as simple as dividing the result by two ?

 

[BvU]

1 Sorry about this. Added that question as well

2 Further to Mark44's comment, the answer I got still seems to be double counting the 7x7, 14x14, and so on

3 Is it as simple as dividing the result by two ?

1 makes my post#2 look dumb

2 Which is what he says:

The condition that "No repetition allowed" likely means that we shouldn't count 7 * 7, 14 * 14, and so on.

3 What result ?

Furthermore, you should also decide if for example, the pair 8,7 is the same as the pair 7,8

$\$

 

[WWGD]

Maybe you can split into two cases for the product ab; when they're both divisible by 7, and when only one is. They're disjoint, i.e., they don't overlap.
The statement Mark44 made generalizes to primes. If p is a prime and p|ab , then p|a or p|b.

 

[SammyS]

Homework Statement: Pick two integers between 1 to 100 (inclusive) whose product is divisible by 7. No repetition allowed
Determine the number of numbers that may be formed this way
Relevant Equations: Basic counting methods

There are 14 integers between 1 to 100 that are divisible by 7

If we used indirect approach, then we would do the total number of possibilities C(100,2) = 4,950
and subtract all numbers' that are indivisible by 7 : C(100-14, 2) = C(86,2) = 3,655

the difference of these two numbers is 4,950 - 3,655 = 1,295

Is this the right answer?

Your insight is greatly appreciated!

I get the same answer as you got, but used a different method of counting.

Also, I assumed, for example, that the pair 7,8 is the same as the pair 8,7. Furthermore, I only considered integers in each pair to be distinct, not allowing pairs such as 7,7 or 98,98 .

 

[WWGD]

I got 1,295 too:
C(14,2) =91 ways of having both being multiples of 7, + 86(14) =1204 ways of having exactly one being a multiple of 7=1,295.

 

[BvU]

So, on a checkers board with 10⁴ fields, there are 14 rows and 14 columns that satisfy "product divisible by 7". You can paint them yellow, and when you're done you have painted 2800 - 14*14 = 2604 fields. To avoid repetition, you don't paint the 14 diagonal fields.

Right answer is 2590

$\$

 

[PeroK]

Homework Statement: Pick two integers between 1 to 100 (inclusive) whose product is divisible by 7. No repetition allowed
Determine the number of numbers that may be formed this way

I interpret this as the number of distinct final products. There are far fewer of those than the results of the combinatorial calculations above. As most final products can be generated in several ways.

 

[BvU]

Why make things simple, eh ?

 

[SammyS]

I interpret this as the number of distinct final products. There are far fewer of those than the results of the combinatorial calculations above. As most final products can be generated in several ways.

Well, yes, if you insist on actually reading what the problem states and complying with that.



This will require some clever analysis of possible prime factors.

 

[WWGD]

So, on a checkers board with 10⁴ fields, there are 14 rows and 14 columns that satisfy "product divisible by 7". You can paint them yellow, and when you're done you have painted 2800 - 14*14 = 2604 fields. To avoid repetition, you don't paint the 14 diagonal fields.

Right answer is 2590

$\$

So either some of us, who arrived at the result of 1,295 half-counted , or you double-counted.
I had this idea of counting all multiples of 7 up to some amount, as the set of products pq, where at least one of p,q , is divisible by 7.

 

[WWGD]

Homework Statement: Pick two integers between 1 to 100 (inclusive) whose product is divisible by 7. No repetition allowed
Determine the number of numbers that may be formed this way
Relevant Equations: Basic counting methods

There are 14 integers between 1 to 100 that are divisible by 7

If we used indirect approach, then we would do the total number of possibilities C(100,2) = 4,950
and subtract all nubmers that are indivisible by 7 : C(100-14, 2) = C(86,2) = 3,655

the difference of these two numbers is 4,950 - 3,655 = 1,295

Is this the right answer?

Your insight is greatly appreciated!

Still, as @PeroK mentioned, if I understood correctly( please correct me if I misunderstood) , would you consider 98=14(7)=49(2) as different numbers obtained as products?
If they're considered different, it seems you may have to use the likes of the Euler Phi function.

 

[BvU]

So either some of us, who arrived at the result of 1,295 half-counted , or you double-counted.

It's a matter of choice; I found the problem statement ambiguous at best.

Furthermore, you should also decide if for example, the pair 8,7 is the same as the pair 7,8

 

[SammyS]

Homework Statement: Pick two integers between 1 to 100 (inclusive) whose product is divisible by 7. No repetition allowed
Determine the number of numbers that may be formed this way.

Relevant Equations: Basic counting methods

Your insight is greatly appreciated!

I think it's pretty clear that @PeroK's interpretation of the problem is probably what was intended.

As he pointed out in Post#10:

I interpret this as the number of distinct final products.
There are far fewer of those than the results of the combinatorial calculations above. As most final products can be generated in several ways.

For example the product of 21 and 84, which is 1,764, also results from multiplying other pairs of integers between 1 to 100 (inclusive).

Those pairs are: {28, 63}, {18, 98}, {36, 49}, and maybe {42, 42} .

So, if counting distinct products is what is intended, then these several pairs taken together all count as giving one single product.

 

[WWGD]

I think it's pretty clear that @PeroK's interpretation of the problem is probably what was intended.

As he pointed out in Post#10:For example the product of 21 and 84, which is 1,764, also results from multiplying other pairs of integers between 1 to 100 (inclusive).

Those pairs are: {28, 63}, {18, 98}, {36, 49}, and maybe {42, 42} .

So, if counting distinct products is what is intended, then these several pairs taken together all count as giving one single product.

And I think something like the Euler Phi function will be involved.

 

[pbuk]

the difference of these two numbers is 4,950 - 3,655 = 1,295

Is this the right answer?

No: for instance you have counted the number 42 three times (2 x 21, 3 x 14, 6 x 7). The correct answer is a little more than half of 1,295.

Right answer is 2590

And you have counted 42 six times (2 x 21, 3 x 14, 6 x 7, 7 x 6, 14 x 3, 21 x 2).

I don't think there is a quick way to find the answer manually, but generating a list without duplicates is something that computers are good at doing.

 

[SammyS]

I don't think there is a quick way to find the answer manually, but generating a list without duplicates is something that computers are good at doing.

Generating your list without duplicates looks more reasonable than trying to use some system of looking at unique prime factorizations to look for and eliminate duplicates.

Also, notice that missing from your lists is 1×42 .

 

[pbuk]

Also, notice that missing from your lists is 1×42 .

Yes, this illustrates well the difficulty of getting things like this right by hand - even if you have 50 years experience of problem solving it is easy to miss obvious things.

But half a dozen lines of code in your favourite programming language gets the right answer straight away.