Math Is Fun Forum

sovixi

Guest

probability problems

I have problems with few exercises?

1. Suppose you have a wire mesh, N units long by M units wide, made up from
   unit squares with wire at the edges.  An ant starts of at the bottom
   left corner (coordinates (0,0)) and wants to get to the top right corner
   (coordinates (M,N)) by following the wires.  How long is the shortest
   route?  How many shortest routes are there? 

   The shortest path is always the sum of N + M. If N = 4 units and M = 5 units then the shortest path will be equal 9 units.

   Whats the answer to the 2nd question?

2.A rabbit is at the start of a line of eleven stepping stones, and wants to
   get to the end of the line.  At each stage he can jump one place (to the
   next stone) or two places (to the next-but-one stone).  For example, he
   could make the journey by the sequence of jumps 221212.  How many different
   sequences of jumps are there that allow him to complete his journey?  What
   would be the result if the rabbit could jump any number of places?

????

3.You are given a sequence s of numbers, in increasing order, for example:

     s = 2, 5, 7, 9, 13, 15.

  You are also given a number n, say n = 16.  You have to try to find two
  numbers x and y from s, such that x+y = n, if such numbers exist.  In this
  example, you could take x = 7 and y = 9.
 
  However, you must do so as efficiently as possible: you must not perform
  more additions than the number of elements in s.  Describe an algorithm to
  do this.

????

Thx

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: probability problems

1) To take the shortest path, the ant may only move right and up, never left or down. Also, it has to move right exactly M times and up exactly N times, taking exactly M+N steps in total. The total number of shortest paths is the number of ways it can move up or right during its (M+N)-step journey, i.e. [sup]M+N[/sup]C[sub]M[/sub] or [sup]M+N[/sup]C[sub]N[/sub] (they’re both the same).

2)

I’ll explain what those combinations mean later, if I have time.

Well, the bottom number is the number of 2-step leaps the rabbit makes and the top number is the the total number of leaps for that number of 2-step leaps – i.e., the rabbit makes
(i) 10 leaps if it makes 0 2-step leaps
(ii) 9 leaps if it makes 1 2-step leap
(iii) 8 leaps if it makes 2 2-step leaps
            ·
            ·
            ·
(vi) 5 leaps if it makes 5 2-step leaps

Last edited by JaneFairfax (2007-04-13 07:27:53)

sovixi

Guest

Re: probability problems

Do you know the answer to the second question?

- What would be the result if the rabbit could jump any number of places?

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: probability problems

Hi sovixi, welcome to the forum. I deleted the new topic you made about the same question, in case you were looking for it.

Unless I'm missing something though, I think that this question will be considerably harder to answer than the previous one. The only way that I can think of is to write down all the sets of jumps that add to 10 and then work out how many combinations there are for each of those.

From before, we have:

1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 2
1, 1, 1, 1, 1, 1, 2, 2
1, 1, 1, 1, 2, 2, 2
1, 1, 2, 2, 2, 2
2, 2, 2, 2, 2

But now there are a lot more that we need to consider as well.

1, 1, 1, 1, 1, 1, 1, 3
1, 1, 1, 1, 1, 2, 3
1, 1, 1, 2, 2, 3
...etc.

I'll try to have a deeper look into this later, if no one else has answered it by then.

---

Why did the vector cross the road?
It wanted to be normal.

sovixi

Guest

Re: probability problems

Ok. I'm waiting for the solution.

I'll try also to do some progress by myself.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: probability problems

I think I've got it now, although it's possible that I might have missed some out.
Below are all the sequences of jumps that add to 10, ignoring order. Then, in each square bracket is the number of ways that the rabbit can arrange that sequence.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1 [1]
1, 1, 1, 1, 1, 1, 1, 1, 2 [9]
1, 1, 1, 1, 1, 1, 1, 3 [8]
1, 1, 1, 1, 1, 1, 2, 2 [28]
1, 1, 1, 1, 1, 1, 4 [7]
1, 1, 1, 1, 1, 2, 3 [42]
1, 1, 1, 1, 1, 5 [6]
1, 1, 1, 1, 2, 2, 2 [35]
1, 1, 1, 1, 2, 4 [30]
1, 1, 1, 1, 3, 3 [15]
1, 1, 1, 1, 6 [5]
1, 1, 1, 2, 2, 3 [60]
1, 1, 1, 2, 5 [20]
1, 1, 1, 3, 4 [20]
1, 1, 1, 7 [4]
1, 1, 2, 2, 2, 2 [15]
1, 1, 2, 2, 4 [30]
1, 1, 2, 3, 3 [30]
1, 1, 2, 6 [12]
1, 1, 3, 5 [12]
1, 1, 4, 4 [6]
1, 1, 8 [3]
1, 2, 2, 2, 3 [20]
1, 2, 2, 5 [12]
1, 2, 3, 4 [24]
1, 2, 7 [6]
1, 3, 3, 3 [4]
1, 3, 6 [6]
1, 4, 5 [6]
1, 9 [2]
2, 2, 2, 2, 2 [1]
2, 2, 2, 4 [4]
2, 2, 3, 3 [6]
2, 2, 6 [3]
2, 3, 5 [6]
2, 4, 4 [3]
2, 8 [2]
3, 3, 4 [3]
3, 7 [2]
4, 6 [2]
5, 5 [1]
10 [1]

Adding all of the bracketed numbers together tells us that there are 512 different sets of jumps that the rabbit can do.

Last edited by mathsyperson (2007-04-18 23:42:46)

---

Why did the vector cross the road?
It wanted to be normal.

whatismath

Member

Registered: 2007-04-10

Posts: 19

Re: probability problems

I got a sum of 512 for the second part of Qu.2.

I think we could look at both parts of Qu.2 the following way
to arrive at dofference equations.
Let A_N = the # of jump sequences from step 1 to step N.
Then A_1 = 1 (no jump at all) and A_2 = 1.
Consider A_N, N > 2.

Part 1: The last jump can be 1 step or 2 steps (but not both).
So A_N = A_(N-1) + A_(N-2) for N > 2.
{A_N} is a Fibonacci sequence,
i.e. A_N = a(alpha^N)+b(beta^N)
where alpha = (1+sqrt(5))/2, beta = (1-sqrt(5))/2
and a, b are determined from A_1 = 1, A_2 =1.

Part 2: The last jump can be any number of 1, 2, .., N-1 steps.
So A_N = A_(N-1) + A_(N-2) + ... + A_1
and by induction A_N = 2^(N-2). In the question, N = 11.

This answer is from an algebraic point of view, i.e. setting up
and solving an equation.

A geometric point of view is to consider which intermediate steps
the rabbit lands. A set of intermediate steps corresponds uniquely
to a sequence of jumps. It starts at step 1 and ends at step N.
A set of intermediate steps is a subset of {2, 3, ..., N-1}.
So there are 2^(N-2) sets of intermediate steps, so is the number
of jump sequences.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: probability problems

Ah, of course. That method is so much nicer than mine. I've just gone and added them up again, and it turns out that my answer was 512 as well anyway.

---

Why did the vector cross the road?
It wanted to be normal.

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: probability problems

The second just fits into Fibonacci Series.

The first is equivalent to fitting M black balls into the line of N white balls.(Is there already a formula for this question?)

---

X'(y-Xβ)=0