Question

how many five digit zip code numbers are possible if the first digit cannot be a four and adjacent digits cannot be the same?

Answer 1

the first digit cant be 4, so there are 9 choices
the second choice can be a 4, but cannot be the same choice as the first digit . so there are 9 choices for the second digit.
for the third digit there are 8 choice, etc
so you get
9X9x8x7

Answer 2

9x9x8x7x6 i mean

Answer 3

Number theory/discrete mathematics?

S = Set of all 5 digit numbers.
D = Set of digits 0-9. Know that D^x = "D cross D cross D.... x times)
\[S = D^5\]\[n(S) = n(D^5) = 100000\]

F = Set of all 5 digit numbers with 4 as the first digit.
\[n(F) = n(D^4) = 10000\]

A = Set of all 5 digit numbers with 2 or more identical adjacent numbers.
\[A = n(D^4) = 10000\](Pretend one of the 4 digits is actually two identical digits next to each other)

We're looking for: \[n(S) - n(F \cup A)\]
\[n(F \cup A) = n(F) + n(A) - n(F intersect A)\] (sorry, there is no upside-down U... wtf)
n(F intersect A) = n(D^3) = 1000
\[ n(F \cup A) = 10000 + 10000 - 1000 = 19000 \]\[n(S) - n(F \cup A) = 100000 - 19000 = 81000\]

Your answer is 81,000 possibilities.

Answer 4

dave thats wrong

Answer 5

oh crap...

Answer 6

you did the complement

Answer 7

I learned the hard way in my discrete mathematics course that a problem that looks extremely simple can turn out to be the most pain-in-the-retricebullsh..t that you never saw coming, and especially if you have to provide a proof..

Answer 8

yeah i did it too fast , one sec

Answer 9

i guess i answered a different question

Answer 10

how did you get ... F intersect A , and how did you find A ,
you said two adjacent numbers is like 00 123 , etc, but there could be more

Answer 11

, ok so you grouped it as (00) 1 2 3 , and then you have 10 ^4 possibilities, beause you can have (00) , 10 ways and then times what exactly

Answer 12

The only thing I'm not positive of in my answer is my evaluation of n(A), so feel free to try and criticize/correct that if you find it is wrong. I'm looking at it now.

Answer 13

yes Im not so sure with your reasoning there

Answer 14

i think you overcounted

Answer 15

Try not to spam the answers, use the chat instead...

Answer 16

lets look at the complement, n(A) = 1 - n(A')

Answer 17

woops, im doing probability.
n(A) = universe - n(A') ,
n(A') = 10*9*8*7*6 ,

Answer 18

universe = n(D^5) = 10^5, so
n(A) = 10^5 - 10*9*8*7*6

Answer 19

you sound like somebody who is either extremely rusty in the topic, or only knows a little.. I'm guessing rusty? you don't subtract cardinalities from the Universe.. the universe is a set and cardinality is an integer

Answer 20

regardless, i think you may be going in the right direction with factorials

Answer 21

the universe is S . , so n(A) = n(S) - n(A')

Answer 22

there ya go

Answer 23

wow, that was so important

Answer 24

omg, the whole problem hinged on that

Answer 25

but let me give you my reasoning, do you agree with n(A')

Answer 26

the cardinality of having no adjacent numbers.
the first choice is 10 digits, then the next can only by 9, then 8 , etc

Answer 27

no because this reasoning doesn't allow a number such as 12121, which does not have any same adjacent numbers

Answer 28

ok

Answer 29

hm okay how about 10*9*9*9*9

Answer 30

for n(A') ?

Answer 31

i think that may be the solution right there.. sooo 65610

Answer 32

yeah, and that would make sense.. now we just have to find the intersection between that and F

Answer 33

which you could do by skipping the whole F deal, and just making it 9^5 i think?

Answer 34

ah no it's wrong

Answer 35

i agree thats 10*9*9*9*9 for n(A')

Answer 36

so n(A) = n(S) - n(A') ,

Answer 37

9^5 = 59, 049

Answer 38

ah maybe it's right.. haha aghhhh

Answer 39

9 choices for first number (can't be 4)
9 choices for second number (can't be first number)
9 choices for third number (can't be second number)
9 choices for fourth number (can't be third number)
9 choices for fifth number (can't be fourth number)

I also verified it with a short program.

Answer 40

right, thats logical

Answer 41

^Thank you for doing what I was too lazy to do...

Answer 42

my first answer assumed no repeating for some reason, woops

Answer 43

thats by multiplication principle

Answer 44

dave, you botched this one pretty bad

Answer 45

and then you tried to insult me. haha

Answer 46

im not even sure about n(F intersect A)

Answer 47

you got 10^3 for that , hmmmm

Answer 48

i asked you about your past experience.. not trying to insult you. this isn't a social playground, we're just trying our best to help somebody get the correct answer here

Answer 49

the person is long gone

Answer 50

who asked the question

Answer 51

anyways, how about finding n(A) now ?

Answer 52

n(A) = 34390

Answer 53

directly finding n(A) is difficult,

Answer 54

dmancine, how did you verify it with a short program?

Answer 55

ok to find n(A) directly you split it into cases,
find when there are exactly 2 adjacent, then exactly 3 adjacent, ... exactly 5 adjacent. these cases are mutuall exclusive and you can use addition rule

Answer 56

http://codepad.org/MMK9wzUM