Posers and Puzzles

Posers and Puzzles

  1. Joined
    04 Aug '01
    Moves
    2408
    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. Joined
    29 Feb '04
    Moves
    22
    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. Joined
    04 Aug '01
    Moves
    2408
    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. Standard membertheangrystudent
    I am MIGHTY!
    The CITY
    Joined
    11 Mar '05
    Moves
    14245
    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. Joined
    04 Aug '01
    Moves
    2408
    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.
    Your answer looks good...don't see any mistakes...your reasoning is certainly right.

    do you recognize what sequence {A(n)} is, assuming we take A(0) = 0?
  6. Joined
    26 Apr '03
    Moves
    26599
    20 Apr '05 23:24
    Originally posted by davegage
    Your answer looks good...don't see any mistakes...your reasoning is certainly right.

    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. Joined
    04 Aug '01
    Moves
    2408
    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. Joined
    21 Apr '05
    Moves
    54
    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. Joined
    26 Apr '03
    Moves
    26599
    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. Joined
    21 Apr '05
    Moves
    54
    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. Non-Sub Recs: 0
    Joined
    08 Apr '05
    Moves
    455
    01 May '05 05:581 edit
    ignore
Back to Top