Exploring the Honeycomb: Calculating Routes from Cell A to Cell B

[fitterj]

Hi there, I've got a bonus question from my calc class that I've been working on. First off I AM NOT LOOKING FOR AN ANSWER. What I really need is for someone to break my algorithm and point me in the right direction so I can keep working on it and hopefully--if it's not too far over my head--I can figure out the correct answer. This is my first time in Calculus since high school in 2003, and I'm pretty sure that this problem actually isn't Calculus at all, but some higher lever of math. Thanks for all help in advance.

Homework Statement

Timmy is a bee. Timmy lives on a honey comb shown below.

A /\/\/\/\/\/\/\/\/\/\B
||\/\/\/\/\/\/\/\/\/\/
|||/\/\/\/\/\/\/\/\/\
|||\/\/\/\/\/\/\/\/\/

(I did my best. The honey comb is two rows. 10 on the first 9 on the second. Cell 1 on the first row is labeled A and cell 10 on the first row is labeled B. Ignore the lines of the left they're just for spacing, because apparently space doesn't work for that.)

Timmy wants to crawl from cell A to cell B. How many ways can he do this without traversing the same cell twice?

The way his bonuses work is if you turn in an answer you get a point. If you somehow manage to get the right answer by some freak occurrence, you get 2. If you work it correctly but aren't sure about the principles behind it you get 3. If you get the right answer and explain the governing principle you get 4. To get five you have to write an algorithm that will extrapolate to a much larger scale.

Homework Equations

If there are any relevant equations I don't know them. Sorry.

The Attempt at a Solution

Ok, so I started off by breaking the honey comb into a smaller version and mapping out the possible routes. The initial honey comb is 3 cells on the first row and 2 on the second. It came out 7 routes. The next honey comb is 4 cells on top and 3 on the bottom. That one mapped out to 19 routes.

What I did next was chart out the routes for each honey comb based on how many cells weren't used in the route.

0|1|2
-------
3|3|1

0|1|2|3
---------
5|9|4|1

(In case it isn't clear, the honey with 3 cells in the first row had 3 routes that used every cell, 3 that used all but one, and 1 that used all but 2[the straight line])

I spent some time looking for patterns and trying to create a working algorithm. Then I noticed that each chart had multiples of 3. The first chart is basically 2*3¹+1. The second is 2*3²+1.

Then I realized that the exponent was the top row minus 2(the starting point and the end point).

I showed my professor my work and explained that I thought this worked but didn't know why 3. He told me I was on the right track, and that I had a 3 point answer.

I have no clue what principles govern this so I decided I should start working on extrapolating the algorithm out to a larger scale. I added another row to the honey comb with 3 cells in the top row that had given me 7 possible routes. I had been thinking that since exponents played a roll in the initial formula and that when cells were added the exponent incremented, then maybe the 2 was actually 2¹. My formula for a 3 row honey comb with 3 cells on top became
2²*3¹+1=13

When I mapped it out I got 14 routes, so it became apparent that the 1 was scaling also. And since 1 is 2⁰ and 2 is 2¹ I ended up coming up with this algorithm:

Let P = the possible routes, let R = the number of rows, let L = the number of cells in the longest row. If R ≥ 2 and L > 2 then:

P = 2^(R-1)*3^(L-2)+2^(R-2).​

I tested it by adding another row to the honey comb with 3 cells on top to give it a total of 4 rows. The expected result was 28 and when I mapped it out, that's what I got. So in the small scale it seems to work. I was wondering if anyone could break this, because I really don't feel like mapping out anymore honey combs to test this. Also if anyone could point me in the right direction of the principles behind this--if I can understand them--that would also be greatly appreciated. Just from googling I think that power rule might be involved, but I don't know anything about it. Like I said before I'm not looking for the correct answer. This was too much fun and if I can do more work on it I'd love to. Sorry this got so wordy. The rules said to show all work. I actually left out some ideas I had that didn't work. Thanks again for all help.

 

[tiny-tim]

hi fitterj! welcome to pf!

(i haven't checked your answer , but …)

the usual way of finding a formula would be by induction, on the number of cells in the top row …

if there are R_n routes for n cells,

what is the relation between R_n+1 and R_n ? ​

 

[fitterj]

Thanks I have no idea what induction is or what subscript does, but I'll know by the end of the weekend.

 

[tiny-tim]

Thanks I have no idea what induction is or what subscript does …

ah, induction basically means finding a formula relating the answer for n+1 cells to the answer for n cells

and we can write the answer as a function of n, eg f(n), though it's more usual to write it with a subscript: f_n

eg if we know f(n+1) = Cf(n), for some constant C, and if we know f(3) = 5, then obviously f(n) = 5C^n-3

(for an example, see http://en.wikipedia.org/wiki/Proof_by_induction#Example)

 

[fitterj]

OK I've got you now. I'm really starting to believe that my formula will extrapolate correctly, but I just can't be sure. I'll try writing over in terms of n and as a function and see if can clean it up a little bit. Thanks a lot man. It helps to be on a solid mathematical footing.