At how many different points could he end up after 10 jumps?

This puzzle is kindly provided by UKMT. A kangaroo is sitting in the Australian outback. He plays a game in which he may only jump 1 metre at a time, either North, South, East or West.
At how many different points could he end up after 10 jumps?
31 Comments
Brian
3/4/2014 03:13:05 pm
11 *11 =121
Reply
Erik
4/4/2014 09:23:41 am
4*sum(1..10)+1=221
Reply
6/4/2014 07:37:05 pm
After n jumps the number of distinct sites is 2n^2+2n+1.
Reply
4/4/2014 11:51:09 am
I will assume that the Kangaroo cannot play quantum games, though that would be fun!! Phasing quantum kangaroos! Likewise, I will assume that the kangaroo cannot take complex jumps, which would also be fun, if slightly less complicated than general quantum jumps.
Reply
Erik
4/4/2014 12:10:05 pm
http://imgur.com/wQxmIt0 Should help explain my take on this.
Reply
Erik
4/4/2014 12:29:25 pm
Oh man, I just saw what I overlooked after reading David's answer a little more closely! Whoops! That's 25 eliminated spaces per quadrant.
Reply
Jim
4/4/2014 01:55:51 pm
121
Reply
Simon
7/4/2014 03:11:18 am
61
Reply
Simon
7/4/2014 03:38:36 am
121 (=61+60)
Reply
Karen
7/4/2014 09:05:08 am
P(10,4) = 151200
Reply
Renee Floyd
28/4/2014 09:14:53 pm
This is what my students did...however, it is not what the majority did
Reply
Tom Thomson
7/4/2014 12:06:11 pm
I decided to solve it generally rather than for 10. To do this, I started from the square containing points with integer x and y coordinates ranging from -n to +n. Excluding the origin (0,0) this contains 4n^2+4n points.Half of these points have (abs(x)+abs(y))>10, so have to be ecluded as they need more than n moves to reach them. The remaining 2n^2+2n points can be viewed as a series of dieamond edges, the outermost having abs(x)+abs(y) = n, the next having abs(x)+abs(y)=n-1 down to the innermost having abs(x)+abs(y)=1 (remember that (0,0) was excluded). Apart from the innermost shell, which has 4 points, each shell has 4 points more than the shell immediately inside it. Points on shells where abs(x)+abs(y) = n mod(2) are reachable in n steps, and other points are not; If n is an even number, this means there are 2n (= 4*n/2) more reachable than unreachable points, so we have to addhalf of 2n to half of 2n*+2n to get the number of reachable points in this centreless square, n^2+2n, and since we left out the origin which is clearly reachable with any wvwn number of moves we have n^2+2n+1, ie (n+1)^2, reachable points altogether. In the case where n is odd, the n-1 outer shells contribute 2(n-1) extra reachable points, and the inner shell contributes another 4, so altogether there are 2n+2 extra reachable points instead of just 2n, so there are (n+1)^2 reachable points in the centreless square, and as the origin is unreachable in an odd number of moves it doesn't need to be added in and we are left with (n+1)^2 for all nonnegative integers n, whether even or odd.
Reply
Richard Catterall
11/4/2014 05:15:14 pm
Nice derivation. The points are those in a square shaped grid bounded by points on the lines x+y=n, x-y=n, x+y=-n and x-y=-n, with a sequence of points in each horizontal line counted by the sum of 1 through to n+1 and back down to 1, giving a total of (n+1)^2. In this case 121.
Reply
Renee Floyd
28/4/2014 09:19:01 pm
Tom,
Reply
Mehtamatics
8/4/2014 08:54:29 am
In two dimensions, with n jumps in one of four directions it is (n+1) squared. In this case 121.
Reply
Tom Thomson
10/4/2014 05:11:00 am
It certainly isn't (n+1)^3 for 3 dimensions, since 2^3 is not 6, and the number of points reachable in 1 move is 6,not 8.
Reply
9/4/2014 01:15:13 am
Agree 11x11 is intuitively clear when looked at as 11 "columns" of 11 points. 11 + 2(10+1) + 2(9+2) + 2(8+3) + 2(7+4) + 2(6+5). Or more simply an 11x11 square of points when rotated 45 degrees. A picture speaks a thousand words. How do I post a picture?
Reply
Paul
24/4/2014 11:13:20 pm
Hi John. Could you post a link to your picture, via dropbox perhaps?
Reply
Tom Thomson
10/4/2014 06:07:28 am
My geometric intuition seems to be completely broken for 3D geometry. I can of course obtain the answer to the 3d problem by brute force, but that's not really satisfactory.
Reply
Tom Thomson
10/4/2014 02:11:50 pm
I guess I was just being stupid - I had forgotten to think about the set excluding the origin. Everything is clean and tidy once he origin is treated as a special case.
Reply
Paul
16/4/2014 12:09:32 am
Thanks everyone, as ever, for your great contributions.
Reply
Paul
16/4/2014 12:11:06 am
Tom, nobody could call you stupid! Your insights are inspiring! And I wasn't expecting the problem to go 3-dimensional. Thanks to you again. Paul
Reply
Trey
16/4/2014 09:33:37 am
k
Reply
Trey
16/4/2014 09:37:19 am
(2n+1)^2
Reply
Trey
17/4/2014 08:07:42 am
After reading the other posts and realizing I made an error in my previous post because I originally agreed with Erik's answer 221. Then after reading Simon's answer I think it is 61.
Reply
Jesse Parete
20/4/2014 06:08:42 pm
2^20
Reply
Jesse Hasty
21/4/2014 04:39:14 pm
(Number of jumps + 1) squared. If the number of jumps is even this includes the origin. In this case 11 squared or 121. The number of squares the 'roo could pass through but not land on is the square of the number of jumps, or 100 here. Hence the total number of squares the 'roo could visit is 221.
Reply
Jeremy Nally
22/4/2014 10:36:20 am
121
Reply
Paul
23/4/2014 12:22:38 am
Thanks Jeremy. Nicely explained.
Reply
Charles Greene
3/8/2014 02:13:00 pm
I get the sides of the square of possible positions to be 11sqrt(2) so I get 241 positions. Can't be back at origin.
Reply
4/8/2014 06:03:50 pm
I plotted out the possible destinations in Q1 (x-axis included, origin excluded, y-axis excluded) and got 30. There are 4 quadrants so 120 + the origin = 121. Yes, they occupy an 11 x 11 grid.
Reply
## Leave a Reply. |
## Puzzle Ideas
If you have an idea for puzzle of the month, then please do let me know. ## Archives
March 2017
Don't forget to check out 'Teach Further Maths' - PowerPoints for Teachers and Students of A-Level Further Maths ...and the brilliant NEW educational card game 'Maths Trumps' |