 Posers and Puzzles

1. 18 Apr '05 00:03
Consider a game played with n identical coins. You are to arrange the coins in either one row or two rows under the following rules:

1. The bottom row cannot have any gaps, i.e., any coin on the bottom row must touch its neighbor(s) if it has a neighbor or neighbors.

2. Any coin placed on the top row must touch two coins from the bottom row.

Let A(n) (for n > 0) be the number of distinguishable arrangements of these n coins allowed under the rules of the game.

Find a general expression for A(n). What sequence do the numbers {A(j)} produce for j = 0,1,2,3,…(for this, take A(0) = 0)?
2. 18 Apr '05 05:051 edit
I don't think I understand.

There is only one way to create one row of n coins.

And if there are k coins in the bottom row, there must be k-1 coins in the top row, right?

Hence n = 2k-1

But this can't be what you mean.

3. 18 Apr '05 06:463 edits
Originally posted by THUDandBLUNDER
I don't think I understand.

There is only one way to create one row of n coins.

And if there are k coins in the bottom row, there must be k-1 coins in the top row, right?

Hence n = 2k-1

But this can't be what you mean.

Yes, I don't know if I explained it too well. Maybe this will help:

There is only one way to create one row of n coins.

Correct.

And if there are k coins in the bottom row, there must be k-1 coins in the top row, right?

No. For example, consider large n. one allowable arrangement would be to have n-1 coins in the bottom row and 1 coin in the top row. There are many distinguishable places this top row coin could sit (namely, n-2 places) and each signifies a different distinguishable arrangement. Another allowable arrangement would be to have n-2 coins in the bottom row and 2 coins in the top row. Again, there are many distinguishable ways these two top row coins could arrange themselves. Etcetera, etcetera.

The top row coins must each touch two bottom row coins, so you are right in saying that if k coins are in the bottom row, then the top row can have at most k-1 coins.

Does this help clarify the problem, THUD?
4. 18 Apr '05 07:45
Here's what I got.
if n = 0, then A(n) = 0 (or possibly one since there is only one way to set up nothing)
if n = 1, then A(n) = 1
if n = 2, then A(n) = 1
When n >= 3,
1 + (n-2) + (n-3)!/[2! * {(n-3)-2}!] + (n-4)!/[3! * {(n-4)-3}!] + ..... + {(n-1)-(m-1)}!/[(m-1)! * {((n-1)-(m-1))-(m-1)}!] + ((n-1)-m)!/[m! * {((n-1)-m)-m}!],
where m = (n/2)-1 if n is even and m = (n-1)/2 if n is odd.
* is a mutiplication sign

I've resisted condensing the formula since it would harder to figure out how I derived it. Plus this isn't the best formate to show math in. But a quick explination might be in order.

The first 1 is for the amount of ways to setup a single row.
The (n-2) is the number of possible ways to set up a upper row with only one coin in that row.
The rest of it is semi-basic probability that isn't easy to write but it's basic form is z!/[y! * (z-y)!] where z is the number of possible positions for coins in the upper row and y is the number of coins in the upper row.
5. 18 Apr '05 08:04
Originally posted by theangrystudent
Here's what I got.
if n = 0, then A(n) = 0 (or possibly one since there is only one way to set up nothing)
if n = 1, then A(n) = 1
if n = 2, then A(n) = 1
When n >= 3,
1 + (n-2) + (n-3)!/[2! * {(n-3)-2}!] + (n-4)!/[3! * {(n-4)-3}!] + ..... + {(n-1)-(m-1)}!/[(m-1)! * {((n-1)-(m-1))-(m-1)}!] + ((n-1)-m)!/[m! * {((n-1)-m)-m}!],
where m = (n/ ...[text shortened]... of possible positions for coins in the upper row and y is the number of coins in the upper row.

do you recognize what sequence {A(n)} is, assuming we take A(0) = 0?
6. 20 Apr '05 23:24
Originally posted by davegage

do you recognize what sequence {A(n)} is, assuming we take A(0) = 0?
Looks like fibonacci - I wonder how he comes into it?
7. 20 Apr '05 23:52
Originally posted by iamatiger
Looks like fibonacci - I wonder how he comes into it?
yep -- Fibonacci...I guess there's just no escaping that sequence.

I was trying to figure out a meaningful way to rationalize why it comes into this problem, but it hasn't come to me yet.
8. 23 Apr '05 03:50
Originally posted by davegage
yep -- Fibonacci...I guess there's just no escaping that sequence.

I was trying to figure out a meaningful way to rationalize why it comes into this problem, but it hasn't come to me yet.
Here's a Fibonacci question:

Since its 2005, of the first 2005 Fibonacci numbers, how many have 2 as their last digit?
9. 23 Apr '05 14:39
Originally posted by elopawn
Here's a Fibonacci question:

Since its 2005, of the first 2005 Fibonacci numbers, how many have 2 as their last digit?
The last digit of each fibonacci number (assuming fib 1 = 0) forms a 60 digit repeating sequence, which contains 4 instances of the number 2.
There are 33 60s in 2005, remainder 25
and of the first 25 fibonacci numbers, only 1 ends in 2

So, of the first 2005 fibonacci numbers, 33*4 + 1 = 133 end in 2.

Here's an interesting fact:
If you count up all the fib numbers that end in each digit, in the 60 term repeating sequence:
There are 4 that end in 0
8 that end in 1
4 that end in 2
8 that end in 3
4 that end in 4
8 that end in 5
4 that end in 6
8 that end in 7
4 that end in 8
8 that end in 9

Can anybody explain why that sequence goes 4,8,4,8,4,8,4,8,4,8?
10. 24 Apr '05 05:041 edit
Originally posted by iamatiger
The last digit of each fibonacci number (assuming fib 1 = 0) forms a 60 digit repeating sequence, which contains 4 instances of the number 2.
There are 33 60s in 2005, remainder 25
and of the first 25 fibonacci numbers, only 1 ends in 2 ...[text shortened]...

Can anybody explain why that sequence goes 4,8,4,8,4,8,4,8,4,8?
That occurance is pretty handy. I'll try to find out the reason for the 8-4 sequence. 😀
11. 01 May '05 05:581 edit
ignore