Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**sovixi****Guest**

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

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] (theyre both the same).

2)

Ill 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)*

Offline

**sovixi****Guest**

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

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.

Offline

**sovixi****Guest**

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

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 51**2** 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.

Offline

**whatismath****Member**- Registered: 2007-04-10
- Posts: 19

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.

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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.

Offline

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,313

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**

Offline

Pages: **1**