Mother of all Questions (1 Viewer)

[OLDMAN]

Who says OLDMAN can't attract attention?

Played basketball with the young son this morning, and the court was filled with hoppers- yes the locusts have finally reached Mudgee. Even without a blade of grass, a grasshopper's orientation after it lands seem pretty random - so its next hopping direction must also be random. Anyway here's the problem which I thought off while my son was beating me 20-11. Its got probability, binomial and possibly (a hint) complex numbers- yes it has the lot!



A grasshopper can only jump adjacent vertices of a square at a time. The probability of jumping to each of two possible adjacent vertices are equal.

a) show that after 9 hops, the grasshopper can't be back in his starting point.
b) find the probability that the grasshopper will be back to his starting vertex after 10 hops.

 

[George W. Bush]

I think the question is like this:

The grasshopper starts on one corner of a square. It can move to any corner which it is linked to by a side. i.e. it can't go directly across. It is equally likely to go to either corner.

 

[Merforga]

A _B
|_|
C D
Dodgy square lol.

If the grasshopper starts at A, it can only hop to B and C, not D and it has equal chance to hop to either B or C when it hops.

 

[Affinity]

Try to exploit some symmetric properties, there's a 2 line answer for both part a and b.

 

[nike33]

 

[Affinity]

nope..
that's way too small..

 

[Affinity]

Hmm.<!-- let the square be ABCD and the grasshopper be at A initially.
let G1={A,C} and G2={B,D}. The grasshopper's position must alternate between G1 and G2, so.. it could only be at A (in G1) after a even number of jumps.. and 9 is not even. so it must be at B or D after 9 moves.

after 1 move the grasshopper is at B or D. and after another 9 moves (10 in total) it must go to A or C. Since A and C are symmetric at this instance, the probability of returning to A is 1/2 -->

 

[Xayma]

Answers in .txt attachment

Originally posted by OLDMAN
Its got probability, binomial and possibly (a hint) complex numbers- yes it has the lot!

I love the fact there wasnt any mention of the prove word

 

[wogboy]

Here's my attempt:

Let x represent the position of the grasshopper such that x=0 at the bottom-left position, x=1 at top-left, x=2 at top-right, and x=3 at bottom-right position. Then as the grasshopper moves to a different vertex, x is either incremented or decremented in modulo 4.

We can assume without loss of generality the grasshopper starts at x=0, and if p is the number of increments and q the number of decrements, then:

x(final) = p-q (mod 4) ...(A)

If the grasshopper does n moves, then:
n = p+q ...(B)

From (A) and (B) we eliminate q to form:
x(final) = 2p - n (mod 4)

if n = 9,
x(final) = 2p - 9 (mod 4)
= 2p + 3 (mod 4)
= 1 (if p is odd) OR 3 (if p is even)
!= 0
So there's no way it can end up back where it started from.

if n=10,
x(final) = 2p - 10 (mod 4)
= 2p + 2 (mod 4)
= 0 (if p is odd) OR 2 (if p is even)
If the grasshopper is to return to it's original spot (x=0) then p must be odd. (i.e. p=1, p=3, p=5, p=7, or p=9)

The probability of p = x is (10Cx)/(2^10)

So the probability of p being odd (hence the grasshopper returning to original position) is:

(10C1 + 10C3 + 10C5 + 10C7 + 10C9)/1024
= 512/1024
= 1/2

(the probability of p being odd is equal to the probability of p being even anyway, due to the symmetry of the binomial distribution for even values of n like n=10).

 

[felafel]

Originally posted by Xayma
Answers in .txt attachment

I love the fact there wasnt any mention of the prove word

nice answer! so concise!

 

[Affinity]

edit: ok try my question... assume its 4 different ways the grasshopper can jump to in a big grid of squares... whats the probability 10 jumps? [/B]

odds are not good.

[17*9!] / [ 2^21]

 

[CM_Tutor]

I like Xayma's approach, but here is a slightly more HSC approach, based on thinking about paths as the permutations of a word - it's also more generalisable.

Take any move in a clockwise direction (ie A -> B -> C -> D -> A) as a C, and an anticlockwise move as an A.

So, one word for a ten step path would be CCACACACCC, and this would start and end on the same spot.

In order to start and end on the same spot, the difference between the number of A's and C's must be a multiple of 4.

Thus, there can be no 9 step path (as only differences possible are 1, 3, 5, 7 and 9).

For 10 step paths that end where they start, we can have 1, 3, 5, 7, or 9 C's, and since C and A are equally likely, this means that the probability is
(¹⁰C₁ + ¹⁰C₃ + ¹⁰C₅ + ¹⁰C₇ + ¹⁰C₉) * (1 / 2)¹⁰ = 512 / 1024 = 1 / 2

These probabilities can be found either from normal binomial probability, or from permutations.

 

[Xayma]

So would a grasshopper on a polygon of 2n sides, have a 1/n chance of returning to its starting spot after 4n+2 jumps? (I cant think of a way to prove it (its hard when I havent done permutations or combinations, but I understand the theory)).

 

[CM_Tutor]

I'd say it'd be (⁴ⁿ⁺²C₁ + ⁴ⁿ⁺²C_n+1 +⁴ⁿ⁺²C_2n+1 + ⁴ⁿ⁺²C_3n+1 + ⁴ⁿ⁺²C_4n+1) / 2⁴ⁿ⁺²

I'm not sure what that simplifies to, but I doubt that it'd be 1 / n.

 

[Xayma]

It doesn't for n=3, so that would mean the approach I used would only be suitable for a square (where the end point can be reached by any "E" point [couldn't think of a better way to phrase it])

 

[George W. Bush]

If we could get OLDMAN to clarify the question a bit as to how many squares there are - the answers jump out at you which is a bit easy for a Mother of All Questions

 

[ND]

Yeh i think we need clarification. Anyway the way i understood it is that the grasshopper is on a grid of squares.

The grasshopper obviously needs an even number of moves to return to his starting point, so 9 can't work.

For it to be back at the starting point after 10 moves, the second 5 moves have to be opposite to the 1st 5 moves (but not in the same order). The first 5 can be any moves, so the answer is (1/4^5)*5! (the 5! is cos the order doesn't matter). Hmm does that work?

 

[nike33]

well when i did it i thought there were lots of squares not just one or watever and got 1/100...i dunno

 

[Merforga]

I got lost after the second line of working ^___^

 

[George W. Bush]

Wait, you had working? :O