Results 1 to 7 of 7

Math Help - 5 Discrete Math Problems (Need by tomorrow! Please Help)

  1. #1
    anu
    anu is offline
    Newbie
    Joined
    Oct 2007
    Posts
    18

    5 Discrete Math Problems (Need by tomorrow! Please Help)

    1)

    (a) Find a recurrence relation for the number of ways to completely cover a 2 x n checkerboard with 1 x 2 dominoes. [Hint: Consider separately the coverings where the position in the top right corner of the checkerboard is covered by a domino positioned horizontally and where it is covered by a domino positioned vertically.]
    (b) What are the initial conditions for the recurrence relation in part (a)?
    (c) How many ways are there to completely cover a 2 x 17 checkerboard with 1 x 2 dominoes?

    2) Find f(n) when n = 2^k, where f satisfies the recurrence relation f(n) = f(n/2) + 1 with f(1)=1.

    3) Suppose that there are n = 2^k teams in an elimination tournament, where there are n/2 games in the first round, with then n/2 = 2^(k-1) winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.

    4) Solve the recurrence relation for the number of rounds in the tournament described in Exercise 3.

    5) Show that f_(0) f_(1) + f_(2) f_(2n-1) + f_(2n) = f_(2n-1) -1 when n is a positive integer.

    Word Doc attached because I don't know how to format Superscript and subscript in this forum. Please refer to it.

    Thank You
    Anu
    Attached Files Attached Files
    Last edited by anu; December 5th 2007 at 01:07 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2007
    From
    Anchorage, AK
    Posts
    276

    Recursive

    On problem 1:

    A. If we have 2 rows and n columns (2xn board) and we put a domino vertically in the upper right corner, then we have the rest of the board equivalent to a 2x(n-1) board. If we put the domino in the corner horizontally, we have to put another horizontal one below it, leaving the rest of the board equivalent to a 2x(n-2) board. This should give you the recurrence relation.
    B. Consider n=1 and n=2 cases
    C. Use your formula (creating a table may be fastest).


    --Kevin C.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Dec 2007
    From
    Anchorage, AK
    Posts
    276

    Recursion

    Problems 2-4:

    2) Consider g(k)=f(2^k). As f(n)=f(\frac{n}{2})+1 with f(1)=1 and \frac{2^k}{2}=2^{k-1}, you can find the recurrence relation for g(k) which is easily solvable, and use that to find solution for f(2^k)=g(k)

    3) Notice that after the first round (of n/2 games) we have n/2 winners left. The rest of the tournament is then equivalent to a tournament of n/2 players. Thus we can find a recurrence relation for the number of rounds f(n) in terms of f(n/2).

    4) Use 2 and 3


    I'm not sure on 5, because of the question of what f(n) is for odd n.

    --Kevin C.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    anu
    anu is offline
    Newbie
    Joined
    Oct 2007
    Posts
    18
    Quote Originally Posted by TwistedOne151 View Post
    On problem 1:

    A. If we have 2 rows and n columns (2xn board) and we put a domino vertically in the upper right corner, then we have the rest of the board equivalent to a 2x(n-1) board. If we put the domino in the corner horizontally, we have to put another horizontal one below it, leaving the rest of the board equivalent to a 2x(n-2) board. This should give you the recurrence relation.
    B. Consider n=1 and n=2 cases
    C. Use your formula (creating a table may be fastest).


    --Kevin C.
    Sorry, but I cannot understand...can u explain more?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Dec 2007
    From
    Anchorage, AK
    Posts
    276

    A diagram

    I'll try to draw a picture of sorts:

    Let us call the number of ways of filling a 2xn board with dominoes F(n)

    Consider a 2xn board (here 2x8):

    _ _ _ _ _ _ _ _
    | | | | | | | | |
    _ _ _ _ _ _ _ _
    | | | | | | | | |
    _ _ _ _ _ _ _ _


    In the upper right corner we could put a domino vertically


    _ _ _ _ _ _ _ _
    | | | | | | | |*|
    _ _ _ _ _ _ _ _
    | | | | | | | |*|
    _ _ _ _ _ _ _ _


    Leaving a space equal to a 2x(n-1) board (here 2X7), so there are F(n-1) ways to fill the board with a domino on the right like this.

    We could instead put a domino horizontally in the corner:


    _ _ _ _ _ _ _ _
    | | | | | | |*|*|
    _ _ _ _ _ _ _ _
    | | | | | | | | |
    _ _ _ _ _ _ _ _


    We would then need to put another below this one (marked by @)


    _ _ _ _ _ _ _ _
    | | | | | | |*|*|
    _ _ _ _ _ _ _ _
    | | | | | | |@|@|
    _ _ _ _ _ _ _ _


    Leaving a 2x(n-2) space, so we have F(n-2) ways to fill the board with a pair of dominoes on the right like this.

    Thus the total number of ways to fill a 2xn board is F(n)=F(n-1)+F(n-2)
    And we have our recurrence relation for part (a).

    --Kevin C.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    anu
    anu is offline
    Newbie
    Joined
    Oct 2007
    Posts
    18
    Thank You for the 1 - 4 problems
    Follow Math Help Forum on Facebook and Google+

  7. #7
    anu
    anu is offline
    Newbie
    Joined
    Oct 2007
    Posts
    18
    Some one please help me on number 5. Do I need to do the proof by induction? If yes, I don't understand how. Is there any other way to do it?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete Math problems
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 5th 2010, 11:05 PM
  2. Couple of Discrete Math problems
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: December 15th 2008, 01:26 AM
  3. 3 Discrete Math Problems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 3rd 2008, 05:13 AM
  4. another discrete math problems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 22nd 2007, 04:03 PM
  5. Urgent Math Help, due tomorrow!!!
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: October 20th 2006, 06:18 AM

Search Tags


/mathhelpforum @mathhelpforum