# Find the number of elements in the intersection of 3 sets

• Oct 23rd 2008, 03:07 AM
alexmahone
Find the number of elements in the intersection of 3 sets
Let A={ $n \in N$ | 5 divides n}
B={ $n \in N$| both n and $\frac {n}{5}$ contain only odd digits}
and C={ $n \in N$ | both n and $\frac {n}{5}$ contain exactly 2006 digits} where N
denotes the set of all natural numbers.
Find the number of elements in $A \cap B \cap C$
• Oct 24th 2008, 11:54 PM
pDeCrunch
Quote:

Originally Posted by alexmahone
Let A={ $n \in N$ | 5 divides n}
B={ $n \in N$| both n and $\frac {n}{5}$ contain only odd digits}
and C={ $n \in N$ | both n and $\frac {n}{5}$ contain exactly 2006 digits} where N
denotes the set of all natural numbers.
Find the number of elements in $A \cap B \cap C$

Since the number needs to stay 2006 digits after dividing by five, the last digit is necessarily 5, 7, or 9. The first two digits need to be 75 in the case of n. 75 is the only last two digit pair that is both odd, is divisible by five, and leads to a five in the last digits place.

Okay I think I have the rest of it now.

So you can have your last digit be 5, 7, or 9. So that means you either get remainder of 0, 2, or 4 after division. Now no number in your sequence of digits can be less than 5 because:

1st case) Your first digit of the 2006 is 5. Remainder is 0. Performing long division means you can only have 5, 7, or 9 in the next slot otherwise you would divide that slot and get 0. So whenever you have a 5 in the previous slot you have 3 choices for the next up until the third to last digit. So when 5 is your first digit you have 3 ^ 2003 possibilities.

2nd case) Your first digit is 7. Remainder is 2 after long division. The next digit must be greater than or equal to 5 otherwise you will get an even number after dividing. Eg. The 2 carries over and let's say you have either a 1 or a 3 in your next slot. 21 or 23 divided by 5 is 4. So again you have a sequence that always has 3 choices per slot. 3 ^ 2003 possibilities.

3rd case) Your first digit is 9. Remainder is 4 after long division. The next digit must be greater than or equal to 5 otherwise you will get an even number after dividing. Eg. The 4 carries over and let's say you have either a 1 or a 3 in your next slot. 41 or 43 divided by 5 is 8. So again you have a sequence that always has 3 choices per slot. 3 ^ 2003 possibilities.

3 * 3 ^ 2003 = 3 ^ 2004 possibilities.