Question

Fool's problem of the day!

A Fascinating counting problem,

In how many ways can we paint a staircase of \( 50 \) steps with two colors green and red such that green steps should never succeed each other?

PS: The answer is enlightening! and it uses one of my favorite thing of mathematics.

Good luck!

Answer 1

How is it 2?

Answer 2

misread question.

Answer 3

doesn't look like a simple counting problem at all.

Answer 4

25 is the maximum number of green steps I think.
25c1 + ... + 24c25? Maybe

Answer 5

I think the same ... but not the latter part.

Answer 6

well, if you want green steps to never succeed each other, then you can only have one green step or no green steps. which leaves 51 possibilities

Answer 7

then one of those green steps must come after the other

Answer 8

No, not necessarily.

Answer 9

After you color them it won't be.

Answer 10

I mean red is different from green.

Answer 11

1+50+(50*48)/2+(50*48*46)/3+ ... should be something very similar like it.

Answer 12

No sorry.

Answer 13

Take time guys, if you haven't seen it before or you are not familiar to what I am thinking it will take some time.

Answer 14

How about, 50c1 + (50c2- 49) + (50c3 -48*49) +...(50c25 - 25*26*27*...*49)?lol

Answer 15

lol

Answer 16

Nooooo, Sorry.

Answer 17

ok I think probability should be like that if there are x steps then probability for paint steps with red color will be n(x)=n(x-1)+n(x-2)
I think. actually i am so weak in probability.

Answer 18

does my formula is correct either? if so then let me progress my calculation. but first let me know about this brain teasing formula guys..

Answer 19

well guys. according to given conditions i think we must use Fibonaci series.

Answer 20

answer version 1.1:
1 + 50 +((48*47)/2 + 2*48) + (2*48*46+48*47*45/3) + ...

Answer 21

@FoolForMath what do you say ... am i pretty close??

Answer 22

I think Fibonacci series sounds like a good call
when I count for 2-5 stairs, I get 3 for 2 stairs, 5 for 3 stairs, 8 for 4 stairs, 13 for 5 stairs, and 21 for 6 stairs

Answer 23

yes. @accessdenied

Answer 24

what do u mean green doesnt succeed each other?

Answer 25

It's Fibonacci series.

Answer 26

for 20 steps 17711 ways are allowed.

Answer 27

similarly calculate for 50 steps.

Answer 28

@Shayaan_Mustafa you google?!

Answer 29

well I ma sure you did.

Answer 30

wait u said counting?!?!

Answer 31

OMG!

Answer 32

Surprisingly the original problem ask for 20 steps.

Answer 33

google is not opening due to proxy server.

Answer 34

i am using proxy to serve openstudy. coz our area internet is blocked. and this problem i had solved in college 2 years ago. that's why i recall it. and not sure but it was for 20 steps.

Answer 35

I agree, that the problem is hard if you haven't solved it before.

Answer 36

i am using proxy to serve openstudy. coz our area internet is blocked. and this problem i had solved in college 2 years ago. that's why i recall it. and not sure but it was for 20 steps.

Answer 37

google is not opening due to proxy server.

Answer 38

Anyways, congrats on solving foo's problem of the day.

Answer 39

Why can't you use proxy for google?

Answer 40

Btw which region is banned?

Answer 41

I don't know from where you got these problem every day and they are really brain teasing.

Answer 42

no it is not banned. due to some server problem some house got stuck.

Answer 43

I have multiple resource :P

Answer 44

lol... not you own brain??? :p

Answer 45

I am good with remixing problems and making it interesting, and no I don't author all the problems I post here.

Answer 46

How did you know fibonacci works here?

Answer 47

Lucas Fibonacci came to home and whispered into my ears. :P

Answer 48

I didn't knew his first name was Lucas, thanks.

Answer 49

@Ishaan94
there are talking about steps so I make a guess. and accessdenied give it a positive direction.

Answer 50

Lol, okay I computed for the small n few terms and I can see the patern

Answer 51

so i can google at last.

Answer 52

i broke it into a smaller problem and counted the number of ways you could arrange the painted green numbers for smaller
i didnt notice that it was fibonacci until i saw it mentioned. :P

Answer 53

You can't guess fibonacci series just like that. It's completely unrelated to this topic or maybe just for me. :/

Answer 54

Fibonacci, Catalan, Prime numbers, Pi are never unrelated to anything ... :P

Answer 55

no... read the condition which FFM has given. then you can guess it. I am electronics engineer. so it is easy to think about brain teasing questions.

because i have those circuits in electronics and solved which have take two weeks in their constructions buddy..

Answer 56

It takes two weeks just to build one circuit? :o

Answer 57

It takes more than two for some.

Answer 58

yes. coz it was for function generator. and that was a team work of mine and my friend.

Answer 59

Oh

Answer 60

FFM is right. coz calculation or circuit analysis is not so easy by hand.

Answer 61

you can always wear gloves though :P

Answer 62

hehehehhe.... noooooOOO lol

Answer 63

The trivial upper bound would be \(2^{50}\) since that's the total number of ways possible. This upper bound can be easily reduced to \[\large 2^{50} - {49\cdot 50 \over 2}\]if the green steps only appear in a single group (when a group has more than one green step).

Answer 64

OOPS!

Answer 65

But I don't feel like this is the right way.

Answer 66

Trust your instincts ;)

Answer 67

Wild guess:

\[\sum_{k=0}^{50}(-1)^k\left(\begin{matrix}50 \\ k\end{matrix}\right)(50-k+1)2^{50-k}\]

Don't ask me to explain this, it's probably too complicated to be correct anyway?

Answer 68

I can almost smell Stirling number ?

Answer 69

I don't know, I've never heard of Stirling numbers before?

Answer 70

you may like to read the discussions.

Answer 71

for n = 1 we have f(n) = 2
G or R

by adding on another "stair" first consider it red giving us f(n)
then consider it green where we have f(n) - (all those beginning with G)
we have f(2) = f(1) + f(1) - 1
=3
RR , GR , RG

let (all those beginning with G) = g(n)
now g(n+1) = f(n) - g(n) (we did this when we considered it beginning with G)
f(n) = f(n-1) +f(n-1) -g(n-1)
=f(n-1) + f(n-1) -( f(n-2) -g(n-2)))

maybe breaking it down like this? im not sure

Answer 72

i broke it down like i said

Answer 73

unless i made some silly mistake

Answer 74

you are genius!!!

Answer 75

thanks for your compliment :)

Answer 76

am i right?

Answer 77

i haven't tried after my method did not work ...

Answer 78

i think i made an error

Answer 79

i think i should give a try too.

Answer 80

got it
i messed up on a sign, and also on my A_r and B_r
it cancels at the end
its the 53rd fibonacci number

Answer 81

for n = 1 we have f(n) = 2
G or R

by adding on another "stair" first consider it red giving us f(n)
then consider it green where we have f(n) - (all those beginning with G)
we have f(2) = f(1) + f(1) - 1
=3
RR , GR , RG

let (all those beginning with G) = g(n)
now g(n+1) = f(n) - g(n) (we did this when we considered it beginning with G)
f(n) = f(n-1) +f(n-1) -g(n-1)
=f(n-1) + f(n-1) -( f(n-2) -g(n-2))

break it down using recursive:
f(n)= 2f(n-1) - g(n-1)
g(n) = f(n-1) - g(n-1)
so we have f(n) = (A_r)f(n-r) + (B_r)(n-r)
we get:

\[A_{r+1} = 2A_{r} + B_{r}\]
\[B_{r+1} = -(A_{r} + B_{r})\]
\[A_1 = 2 \]
\[B_1 = -1\]

a few calculations reveal the Fibonacci pattern here
i then showed inductively that A_r is the (r+ 3)th Fibonacci number and B_r is negative the (r+1)th fib number

then let n = 50 , let r = n-1, and we already know f(1) and g(1)
some cancellations leave us with 53rd fib number