# Discrete Math: Integers

A US Social Security number is a nine-digit number. The first digit (or digits) may be zero.

a) How many US Social Security numbers are available?

b) How many US Social Security numbers are odd?

c) How many US social security numbers read the same backward and forward (eg 350767053)?

These 4-digit numbers cannot start with zero.

a) How many 4-digit numbers do not contain number 5 among its digits?

b) How many 4-digit numbers contain at least one number 5 among its digits?

c) How many 4-digit numbers contain exactly one number 5 among its digits?

Prove that if a is an odd integer, then a^2 + 7 is divisible by 4.

Read very carefully each of these sentences. Then, complete them:

a) The only integer which is divisible by every other integer is...

b) The integers that divide all prime numbers are ... and ...

c) If p is a prime number, it has ... positive divisors, and ... integer divisors.

d) (See the attachment for the equation)

e) Which one is larger, 2^1000 or 500! ? The answer is ...

f) The set {{2,6},{3,6}} has exactly ... elements. Does it coincide with {2,3,6}?

Prove that 99^4 divides 100!-99!

#### Solution Preview

Please see the attachments.

For each digit placeholder we can choose a number from 0 to 9 independent of the other placeholders.

Say we have only one place holder. The number of possibilities is obviously 10.

Now we add another placeholder. We first put "0" for the first placeholder, and then run all the possible numbers for the second placeholder. We get 10 possible combinations.

Then we change the first placeholder to "1". We get 10 new combinations.

We can continue to change the first placeholder, and each time we get 10 new combinations.

Hence, for placeholders, we have different combinations.

If we add a third placeholder, we can take the previous 100 combinations and add another digit. So we now have possible combinations.

We see that the number of combinations is , where n is the number of placeholders.

We can prove it by induction. Assume this is true for n and we add the placeholder. Now the number of possible combinations is:

In the Social Security numbers there are placeholders, hence the number of possible combinations is:

There are 1 billion possible combinations.

In general we can say that if we have placeholders, each can hold set ...

#### Solution Summary

Discrete mathematics integers are examined. How many United States social security numbers are determined.