Page 1 of 2 12 LastLast
Results 1 to 15 of 20

Math Help - Need help with proof

  1. #1
    Junior Member
    Joined
    Apr 2010
    Posts
    29

    Need help with proof

    Hi, not sure if this is the right category just saw logic and set theory in the info so I assumed that this would be the proper place.

    I'm currently taking a class called MAT231 Sets, functions, and relations.

    I honestly can't remember when I ever did a proof before (think high school but it was skippable on the exam).

    Below is the assigned worksheet I'm suppose to do #1,#2.
    #3 and #4 are suppose to be more challenging ones that you can attempt.

    Need help with proof-proof-worksheet.jpg

    I've tried to attempt parts of #1

    a. Yes, there is 64 total squares with even dimensions of 8 x 8.

    8^2 = 2x
    x= 32

    b. No, if you remove opposite corners then the dimensions would change. Creating a 6 by 6 inner square with a border of of 7 on each side. The dominoes can fill the 6 by 6 inner square but cannot cover the "odd" dimensions of the border.

    Let S = inner square
    S = 6^2
    S= 36

    Lets T = border
    T= 7+7+7+7 = 28....Error in my logic this contradicts since 28 is divisible by 2 (length of a domino) but I don't believe the board can be complexly covered because of the change in dimensions.

    c. No, the demensions are odd.

    d.
    When m and n are both even natural numbers.
    When m or n is an even natural number.

    e. When m is an odd natural number and n is an even natural number. (or viseversa)

    I really need help this is the first assignment and all we talked about briefly in the first class was "conjectures" which we were told is an educated guess. I lack how to find the logic for the statements I need.

    #2

    a. 1 = 1; 1 + 3 = 4; 1 + 3 + 5 = 9; 1 + 3 + 5 + 7 = 16;

    b. 1 + 3 + ... + (2n + 1) = ???

    c. 1 = 1; 1 + 8 = 9; 1 + 8 + 27 = 36; 1 + 8 + 27 + 64 = 100;

    d. 1 + 8 + ... + n^3 = ???
    Last edited by Jay23456; August 28th 2012 at 09:25 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help with proof

    Quote Originally Posted by Jay23456 View Post
    a. Yes, there is 64 total squares with even dimensions of 8 x 8.

    8^2 = 2x
    x= 32
    It is not enough to show that the number of squares on the board is divisible by the number of squares on a domino. As you said later, the number is still divisible if you remove the corner squares, but in that case there is no perfect covering.

    If you need to prove a claim saying that something (a perfect covering in this case) exists, a typical way is to exhibit a required object (witness of the claim) and prove that it satisfies the necessary properties. In this case, you need to describe in more details how you can cover a full board.

    Proving that something does not exists is trickier because instead of exhibiting one witness you need to show that any supposed witness does not work. This can be done as follows. Find a property satisfied by all parts of the board that have a perfect covering (i.e., a property satisfied by all parts that can be covered fully and with no overlapping) and show that the 8 x 8 board with the opposite corner squares removed does not satisfy this property.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2010
    Posts
    29

    Re: Need help with proof

    was gonna say the board on a 8 by 8 was symmetrical which would be correct to dismiss when you remove the squares from opposite corners but then again that would be contradicted by the
    7 by 7 board which can't be perfectly covered. Hmm...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help with proof

    Quote Originally Posted by Jay23456 View Post
    was gonna say the board on a 8 by 8 was symmetrical which would be correct to dismiss when you remove the squares from opposite corners but then again that would be contradicted by the
    7 by 7 board which can't be perfectly covered. Hmm...
    This does not mean much unless you define "symmetric" and prove its relationship to perfect covering. A board with the opposite corners removed is symmetric with respect to the line going from one removed corner to the other.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2010
    Posts
    29

    Re: Need help with proof

    Quote Originally Posted by emakarov View Post
    If you need to prove a claim saying that something (a perfect covering in this case) exists, a typical way is to exhibit a required object (witness of the claim) and prove that it satisfies the necessary properties. In this case, you need to describe in more details how you can cover a full board.
    Trying to focus on this point on how to describe how to cover a full board.

    my thoughts:
    You can cover the whole board if there is n amount of squares (where n is any even integer) and if at least one side of the board is an even natural number.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,393
    Thanks
    1845

    Re: Need help with proof

    Every domino, whether placed vertically or horizontally, covers one white and one black square. How many white and black squares are there on the original board? How many after the two corner squares are cut off?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help with proof

    Quote Originally Posted by emakarov View Post
    If you need to prove a claim saying that something (a perfect covering in this case) exists, a typical way is to exhibit a required object (witness of the claim) and prove that it satisfies the necessary properties. In this case, you need to describe in more details how you can cover a full board.
    Quote Originally Posted by Jay23456 View Post
    Trying to focus on this point on how to describe how to cover a full board.

    my thoughts:
    You can cover the whole board if there is n amount of squares (where n is any even integer) and if at least one side of the board is an even natural number.
    It is sufficient to require that at least one side is an even number because then the total number of squares is also even. Your claim is true, but in my remark I was saying that a constructive proof of existence must describe a witness (perfect covering). In the case of problem 1a (8 x 8 board), each row can be covered by 4 horizontal dominoes. A reader is not expected to read a claim about existence, think an hour and exclaim, "Yes, it is obvious!"
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Apr 2010
    Posts
    29

    Re: Need help with proof

    @HallofIvy ahh wow didn't even take that into consideration its like the most basic things you look over. Thanks!

    @emakarov You said my claim was true so should i add it to my proof, or was what you said after about the reader should have to think hours then realize it apply to it?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help with proof

    Sorry, but it seems that you missed every thing I said in this thread.

    Quote Originally Posted by Jay23456 View Post
    @HallofIvy ahh wow didn't even take that into consideration its like the most basic things you look over.
    I tried to hint to this in post #2 when I said:
    Quote Originally Posted by emakarov
    Find a property satisfied by all parts of the board that have a perfect covering (i.e., a property satisfied by all parts that can be covered fully and with no overlapping) and show that the 8 x 8 board with the opposite corner squares removed does not satisfy this property.
    Next,

    Quote Originally Posted by Jay23456 View Post
    @emakarov You said my claim was true so should i add it to my proof, or was what you said after about the reader should have to think hours then realize it apply to it?
    Quote Originally Posted by emakarov
    A reader is NOT expected to read a claim about existence, think an hour and exclaim, "Yes, it is obvious!"
    I said that in problem 1a you need to explicitly describe the covering; you have not done so. Instead, you started speculating about symmetry and about more general sufficient conditions for the existence of perfect covering.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Apr 2010
    Posts
    29

    Re: Need help with proof

    Ah yes sorry I did read what you said but it didn't click that the opposite corners were the same color tile.
    Heres my rework of #1

    Given:
    • 8 by 8 chess board.
    • A single domino covers 2 squares.


    Statements:
    • There are 64 squares total.
    • 32 white and 32 black squares.
    • There are 4 white and black squares per row.
    • A domino must go on 1 white square and 1 black square.
    • If at least one side is an even number then the total area will be even.



    a) Yes, the board can be perfectly covered by the dominoes because there are an equal amount of tiles and both of the sides are even numbers.
    b) No, when you remove two opposite corners you remove to 2 tiles from black or white, disproportioning the even white to black ratio.
    c) No, a 7 by 7 board will not produce an even area.
    d) When m and n are both even natural numbers. When m or n is an even natural number.
    e) When m is an odd natural number and n is an even natural number. (or vice versa)
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help with proof

    Quote Originally Posted by Jay23456 View Post
    Given:
    • 8 by 8 chess board.
    • A single domino covers 2 squares.


    Statements:
    • There are 64 squares total.
    • 32 white and 32 black squares.
    • There are 4 white and black squares per row.
    • A domino must go on 1 white square and 1 black square.
    • If at least one side is an even number then the total area will be even.
    If you started talking about a 8 x 8 board, it is better not to shift to a board of an arbitrary size in the last statement.

    Quote Originally Posted by Jay23456 View Post
    a) Yes, the board can be perfectly covered by the dominoes because there are an equal amount of tiles and both of the sides are even numbers.
    No. First, you still did not describe the covering. Second, you cannot rely on the fact that having equal numbers of black and white tiles and even size implies the existence of a perfect covering because you have not proved it yet. Nor are you supposed to prove it in (a).

    Quote Originally Posted by Jay23456 View Post
    b) No, when you remove two opposite corners you remove to 2 tiles from black or white, disproportioning the even white to black ratio.
    It is not clear why changing the ratio of white and black squares prevents the covering. This has not been explicitly stated or proved.

    Quote Originally Posted by Jay23456 View Post
    c) No, a 7 by 7 board will not produce an even area.
    So what? You have not stated or proved that a board with an odd number of squares does not have a perfect covering.

    Quote Originally Posted by Jay23456 View Post
    d) When m and n are both even natural numbers. When m or n is an even natural number.
    So, which of the two statements is the answer?

    Quote Originally Posted by Jay23456 View Post
    e) When m is an odd natural number and n is an even natural number. (or vice versa)
    This has not been proved.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Apr 2010
    Posts
    29

    Re: Need help with proof

    Quote Originally Posted by emakarov View Post
    If you started talking about a 8 x 8 board, it is better not to shift to a board of an arbitrary size in the last statement.

    No. First, you still did not describe the covering. Second, you cannot rely on the fact that having equal numbers of black and white tiles and even size implies the existence of a perfect covering because you have not proved it yet. Nor are you supposed to prove it in (a).
    I thought i did describe the covering by stating there is 64 total squares (32 black, 32 white) and that a domino must go on 1 white and 1 black. Or does this not describe it? (sorry I'm knew to this)

    Quote Originally Posted by emakarov View Post
    It is not clear why changing the ratio of white and black squares prevents the covering. This has not been explicitly stated or proved.
    Should I write that getting rid of two white squares would make 62 total squares 32 black and 30 white and a domino must go on a white and a black and if we attempted to do this there would be two white tiles remaining.
    Quote Originally Posted by emakarov View Post
    So what? You have not stated or proved that a board with an odd number of squares does not have a perfect covering.
    How would I show this with a table? like if both are even, both are odd, one is even?(same response for last one)

    Quote Originally Posted by emakarov View Post
    So, which of the two statements is the answer?
    I thought either statement could of worked

    Quote Originally Posted by emakarov View Post
    This has not been proved.
    How would I show this with a table? like if both are even, both are odd, one is even?

    Really appreciate your help btw sorry i am a bit slow on the uptake.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help with proof

    Quote Originally Posted by Jay23456 View Post
    I thought i did describe the covering by stating there is 64 total squares (32 black, 32 white) and that a domino must go on 1 white and 1 black. Or does this not describe it?
    No, it does not. You described a property that a covering would have if it existed, but it is not clear that such covering exists. When you define an object, you have to really construct it; it is not enough to describe some desired properties.

    For example, it is correct to say, "Let x = 1." This unambiguously defines x. It is not OK to say, "Let x be the number such that x2 = 1"; however, one can say, "Let x be a number such that x2 = 1." We know that two such numbers exist, so x can be 1 or -1. It is definitely not OK to say, "Let x be a number such that x2 = -1." We know that such number does not exist. It is also not OK to say, "Let x be a number such that x4 + 3x3 - 2x2 - 5x + 1 = 0." At first reading, it is not obvious at all that such x exists.

    As I said in post #7, an appropriate description of a perfect covering of a 8 x 8 board would be, "Place 4 horizontal dominoes next to each other on each row."

    If your description above were enough, then by the same logic we could construct a perfect covering of a board where three white and three black squares were removed (and the board did not fall apart). However, this is not always possible (see here). What about a board where one white and one black, but not necessarily corner, squares are removed? Then there is always a perfect covering. This is known as Gomory's theorem, and its proof is definitely more complicated than your description above.

    Quote Originally Posted by Jay23456 View Post
    Should I write that getting rid of two white squares would make 62 total squares 32 black and 30 white and a domino must go on a white and a black and if we attempted to do this there would be two white tiles remaining.
    Yes, this would be a good explanation.

    Quote Originally Posted by Jay23456 View Post
    How would I show this with a table? like if both are even, both are odd, one is even?(same response for last one)
    I am not sure a table is necessary. The fact there is no perfect covering for a 7 x 7 board does not have a perfect covering is pretty obvious, but it still needs to be explained, for example, by saying that any domino covering occupies an even number of squares.

    Quote Originally Posted by Jay23456 View Post
    I thought either statement could of worked
    Yes, but in this case were are looking at how many things we need to check to guarantee the existence of a perfect covering. It is better to verify that one dimension is even; that alone would guarantee a covering regardless of the second dimension. And since this is a claim of existence, you are supposed to construct a covering similar to how it was done for the 8 x 8 case.

    Your condition guaranteeing the existence of a covering in (d) is correct, but, again, since this is a claim of existence, you need to describe how you construct a covering in this case.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Apr 2010
    Posts
    29

    Re: Need help with proof

    Ah I see for d you want the simplest requirement to be met (a minimum check) I added one statement in blue
    and rewrote my answers hope they are more correct now.
    Given:
    • 8 by 8 chess board.
    • A single domino covers 2 squares.


    Statements:
    • There are 64 squares total.
    • 32 white and 32 black squares.
    • There are 4 white and black squares per row.
    • A domino must go on 1 white square and 1 black square.
    • If at least one side is an even number then the total area will be even.
    • In order for a perfect covering there must be a side with an even length, because a domino covers 2 (an even number) spaces.





    a) Yes, In order for the board to be completely covered there must be an even amount of tiles on one dimension because a domino takes up an even amount of spaces (2), in this case both dimensions are even (8 by 8) so you can lay four dominos across a row and repeat for each other row.
    b) No, getting rid of two white squares would make 62 total squares 32 black and 30 white and a domino must go on a white and a black and if we attempted to do this there would be two white tiles uncovered remaining.
    c) No, a domino occupies an even amount of tiles. Neither dimension had an even amount.

    d) When m or n is an even natural number.

    e) When m is an odd natural number and n is an even natural number (or vice versa), because the dimensions multiplied would be an even amount of total space and when removing corners you would remove 1 of each (black & white) tile.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help with proof

    Quote Originally Posted by Jay23456 View Post
    In order for a perfect covering there must be a side with an even length, because a domino covers 2 (an even number) spaces.
    This is a correct claim, but a wrong explanation. In a given row not all dominoes have to be placed horizontally. There may be one vertical domino and several horizontal ones; the total width would be odd. You repeat this wrong explanation two more times.

    Quote Originally Posted by Jay23456 View Post
    b) No, getting rid of two white squares would make 62 total squares 32 black and 30 white and a domino must go on a white and a black and if we attempted to do this there would be two white tiles uncovered remaining.
    You probably mean two black tiles remaining.

    Quote Originally Posted by Jay23456 View Post
    c) No, a domino occupies an even amount of tiles. Neither dimension had an even amount.
    This explanation is not sufficient as explained above.

    Quote Originally Posted by Jay23456 View Post
    e) When m is an odd natural number and n is an even natural number (or vice versa), because the dimensions multiplied would be an even amount of total space and when removing corners you would remove 1 of each (black & white) tile.
    What you are saying is correct, but I will repeat this just one more time: to prove that something exists you need to explicitly construct it.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 12:13 PM
  2. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  3. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum