## FoolForMath 3 years ago Just another super easy problem, A $$5\times 5$$ square is made of square tiles of dimensions $$1\times 1$$. A mouse can leap along the diagonal or along the side of square tiles. In how many ways can the mouse reach the right lower corner vertex of the square from the lower left corner vertex of the square leaping exactly $$5$$ times?

1. apoorvk

Is it 7 by any chance?

2. FoolForMath

No, but it's a multiple of 7 ;)

3. apoorvk

make that 14.. or am i lolling myself again?

4. Ishaan94

idk why but i feel it's 21.

5. Ishaan94

I havent solved it yet, just a guess.

6. apoorvk

|dw:1338132939113:dw| need one more.

7. Ishaan94

Why did the tiled square got deleted? It was helpful.

8. Ishaan94

Now I will have to draw on my notebook :/

9. experimentX

|dw:1338133230250:dw| Not so better than before!!

10. apoorvk

|dw:1338133213060:dw| okay 5 more - i learnt not to 'derive' answers lol.

11. apoorvk

BUGG!!!!^^

12. apoorvk

|dw:1338133822413:dw|

13. Ishaan94

Instead of 5, we can try three and four to get a generalized pattern. Counting isn't the right way.

14. Ishaan94

For me at least. I keep messing up my count.

15. apoorvk

|dw:1338134551987:dw|

16. TuringTest

17. apoorvk

Cool^^

18. TuringTest

lol

19. TuringTest

...now somebody analyze it

20. apoorvk

I got 21 - and am pretty sure.

21. TuringTest

I'd like to show it though. I wanna figure a way to count based on the number of horizontal moves the mouse makes, like there is only 1 possible path with 5 moves horizontal|dw:1338135897949:dw|4 not possible... how many ways can he do it if he goes 3 horizontal steps?\ at least that's how I'm thinking...

22. TuringTest

|dw:1338136237586:dw|I see 3 possibilities along the bottom and one if he goes along the middle totaling 4 now it would be nice to find a pattern rather than count for 2

23. TuringTest

no, there are more... I made a mistake

24. apoorvk

That is what I drew above - the black lines are the movements along the grid.

25. TuringTest

I think you are right @apoorvk I just can't prove it

26. Ishaan94

How do we know it's 21?

27. Ishaan94

Are you sure of your counting?

28. Ishaan94

|dw:1338137956244:dw|

29. Ishaan94

The triangle doesnt trace this path.

30. TuringTest

what path is that o-0 ? it's all corner moves, right?

31. apoorvk

It's 21 for this - I am sure of this - checked that. How do we generalise this though?

32. Ishaan94

What do you mean by corner move?

33. TuringTest

" In how many ways can the mouse reach the right lower corner vertex from the lower left corner vertex of the square" he can't start in the middle of a square, only a corner, so he cannot move vertically at all

34. TuringTest

...only diagonally

35. Ishaan94

" A mouse can leap along the diagonal or along the side of square tiles."

36. TuringTest

yeah, but try it if he makes a vertical move he will never reach the lower left corner

37. TuringTest

he's got to stay on the grid is the point I think

38. Ishaan94

|dw:1338138315764:dw|

39. TuringTest

|dw:1338138438753:dw|" ...from the lower left corner vertex of the square " I took that to mean that he starts at this point|dw:1338138495546:dw|

40. TuringTest

and how is this|dw:1338138529062:dw|moving "along the edge of the tile"? I'd say that's moving through the middle of it

41. Ishaan94

oh

42. Ishaan94

@FoolForMath is offline :/

43. TuringTest

he gave me a medal for my drawing, so I think that would mean I interpreted it correctly how did you read it @apoorvk ?

44. apoorvk

yeah ofcourse on the grid!! The instructions are pretty clear about that - it's about "vertex-to-vertex" jump, not from "spot-to-spot".

45. Ishaan94

I see. I was doing it wrong all along :/ :( such a wasted effort :/

46. TuringTest

but that's great, now you can do it correctly for us @Ishaan94 :D

47. FoolForMath

21 is the right answer. The general solution is also amazing :D Thanks to M.SE I found this one: http://en.wikipedia.org/wiki/Motzkin_number http://math.stackexchange.com/questions/150420/

48. experimentX

lol ... that wasn't easy!! enlightening though!!

49. FoolForMath

I agree :D