# Thread: Help in combinatorics exercise

1. ## Help in combinatorics exercise

Hey everyone I'm stuck in the exercise, I will be happy to work out a solution
Find how many integers - n, have the attribute:
n is divisible by 7 and is not divisible by any natural number - k that sustains:
Thanks friends.

2. ## Re: Help in combinatorics exercise

You are looking for numbers that have 7 as a factor, but do not have 2,3, or 5, as a factor.

Let $A_k = \{n \in \mathbb{N}|1 \le n \le 7770\text{ and }k\text{ divides }n\}$

You are looking for:

\begin{align*}\left|A_7 \setminus (A_2 \cap A_3 \cap A_5)\right| = & |A_7| - |A_{7\cdot 2}| - |A_{7\cdot 3}| - |A_{7\cdot 5}| \\ & + |A_{7\cdot 2\cdot 3}| + |A_{7\cdot 2\cdot 5}| + |A_{7\cdot 3\cdot 5}| \\ & - |A_{7\cdot 2\cdot 3\cdot 5}|\end{align*}

This is because if $p,q$ are distinct primes, then $A_p\cap A_q = A_{pq}$, and also from the Inclusion/Exclusion principle. Additionally, for any prime $p$, you have:

$|A_p| = \left\lfloor \dfrac{7770}{p} \right\rfloor$

I hope you get the idea. So, the answer is:

$\dfrac{7770}{7}-\left(\dfrac{7770}{7\cdot 2} + \dfrac{7770}{7\cdot 3} + \dfrac{7770}{7\cdot 5}\right) + \left(\dfrac{7770}{7\cdot 2\cdot 3} + \dfrac{7770}{7\cdot 2\cdot 5} + \dfrac{7770}{7\cdot 3\cdot 5} \right) - \dfrac{7770}{7\cdot 2\cdot 3\cdot 5} = 296$

Edit: To verify, you can use Excel.
In cell A1, type the formula: =MOD(ROW(),2)>0
(this will be TRUE if the row number is NOT divisible by 2)
In cell B1, type: =MOD(ROW(),3)>0
C1: =MOD(ROW(),4)>0
D1: =MOD(ROW(),5)>0
E1: =MOD(ROW(),6)>0
F1: =MOD(ROW(),7)=0
(notice this one you want it to be equal to zero because that means the row number is divisible by 7)
G1: =MOD(ROW(),8)>0
H1: =MOD(ROW(),9)>0
I1: =MOD(ROW(),10)>0
J1: =AND(A1:I1)
Then select cells A1:J1 and copy the formulas down to row 7770. Then, in any open cell, add the formula: =COUNTIF(J1:J7770,TRUE) and it will tell you how many rows satisfied the conditions you set for divisibility.

3. ## Re: Help in combinatorics exercise

Thanks a friend for helping me very much

4. ## Re: Help in combinatorics exercise

Edit: To verify, you can use Excel.
In cell A1, type the formula: =MOD(ROW(),2)>0
(this will be TRUE if the row number is NOT divisible by 2)
In cell B1, type: =MOD(ROW(),3)>0
C1: =MOD(ROW(),4)>0
D1: =MOD(ROW(),5)>0
E1: =MOD(ROW(),6)>0
F1: =MOD(ROW(),7)=0
(notice this one you want it to be equal to zero because that means the row number is divisible by 7)
G1: =MOD(ROW(),8)>0
H1: =MOD(ROW(),9)>0
I1: =MOD(ROW(),10)>0
J1: =AND(A1:I1)
Then select cells A1:J1 and copy the formulas down to row 7770. Then, in any open cell, add the formula: =COUNTIF(J1:J7770,TRUE) and it will tell you how many rows satisfied the conditions you set for divisibility.[/QUOTE]

This site shows me something interesting that I did not know, can you please repeat the last part?

5. ## Re: Help in combinatorics exercise

Originally Posted by yossa
Edit: To verify, you can use Excel.
In cell A1, type the formula: =MOD(ROW(),2)>0
(this will be TRUE if the row number is NOT divisible by 2)
In cell B1, type: =MOD(ROW(),3)>0
C1: =MOD(ROW(),4)>0
D1: =MOD(ROW(),5)>0
E1: =MOD(ROW(),6)>0
F1: =MOD(ROW(),7)=0
(notice this one you want it to be equal to zero because that means the row number is divisible by 7)
G1: =MOD(ROW(),8)>0
H1: =MOD(ROW(),9)>0
I1: =MOD(ROW(),10)>0
J1: =AND(A1:I1)
Then select cells A1:J1 and copy the formulas down to row 7770. Then, in any open cell, add the formula: =COUNTIF(J1:J7770,TRUE) and it will tell you how many rows satisfied the conditions you set for divisibility.

This site shows me something interesting that I did not know, can you please repeat the last part?
I'm not sure what you are asking. If you do not have Microsoft Excel, then any OpenOffice spreadsheet will work.

6. ## Re: Help in combinatorics exercise

Originally Posted by SlipEternal
I'm not sure what you are asking. If you do not have Microsoft Excel, then any OpenOffice spreadsheet will work.
I'll explain myself, I have Microsoft Excel, I was able to place everything in a simple phase a - "Then select cells A1:J1 and copy the formulas down to row 7770. Then, in any open cell, add the formula: =COUNTIF(J1:J7770,TRUE) and it will tell you how many rows satisfied the conditions you set for divisibility." not so figured out

7. ## Re: Help in combinatorics exercise

Select cells A1:J1. Right click and choose Copy (or CTRL+C on the keyboard). On the keyboard, press CTRL+G (this will bring up a dialog that says GoTo in the title. In the Reference line, put A7770. Now, while holding the Shift key (do not let go), do the following:
1. Press and release the End key
2. Press and release the Up arrow key
3. Press and release the right arrow key nine times (so you will have every cell in the range A1:J7770 highlighted).

Release the Shift key, right click, and press Paste (or CTRL+V on the keyboard).

8. ## Re: Help in combinatorics exercise

Originally Posted by SlipEternal
Select cells A1:J1. Right click and choose Copy (or CTRL+C on the keyboard). On the keyboard, press CTRL+G (this will bring up a dialog that says GoTo in the title. In the Reference line, put A7770. Now, while holding the Shift key (do not let go), do the following:
1. Press and release the End key
2. Press and release the Up arrow key
3. Press and release the right arrow key nine times (so you will have every cell in the range A1:J7770 highlighted).

Release the Shift key, right click, and press Paste (or CTRL+V on the keyboard).

i get it thanks