Thread: 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.



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 = ???

Originally Posted by Jay23456

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.

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...

Originally Posted by Jay23456

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.

Originally Posted by emakarov

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.

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?

Originally Posted by emakarov

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.

Originally Posted by Jay23456

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!"

@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?

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

Originally Posted by Jay23456

@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:

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,

Originally Posted by Jay23456

@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?

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.

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)

Originally Posted by Jay23456

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.

Originally Posted by Jay23456

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).

Originally Posted by Jay23456

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.

Originally Posted by Jay23456

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.

Originally Posted by Jay23456

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?

Originally Posted by Jay23456

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

This has not been proved.

Originally Posted by emakarov

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)

Originally Posted by emakarov

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.

Originally Posted by emakarov

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)

Originally Posted by emakarov

So, which of the two statements is the answer?

I thought either statement could of worked

Originally Posted by emakarov

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.

Originally Posted by Jay23456

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 x² = 1"; however, one can say, "Let x be a number such that x² = 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 x² = -1." We know that such number does not exist. It is also not OK to say, "Let x be a number such that x⁴ + 3x³ - 2x² - 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.

Originally Posted by Jay23456

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.

Originally Posted by Jay23456

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.

Originally Posted by Jay23456

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.

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.

Originally Posted by Jay23456

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.

Originally Posted by Jay23456

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.

Originally Posted by Jay23456

c) No, a domino occupies an even amount of tiles. Neither dimension had an even amount.

This explanation is not sufficient as explained above.

Originally Posted by Jay23456

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.