Discrete Mathematics!

[Julian]

Doing an extra assignment to help boost my grade a bit, this isn't too hard, but could really use some help.

No, I don't want you to do all of it to me, just point me in the right direction or help explain it a little bit.

Also, I only need to do 4 out of these 6 problems, but I'd like to know how to be able to do all of them for the final.


Problem 1:
Consider a 7 x 7 checkerboard with the squares at the four corners removed (so that the remaining board has 45 squares). Is it possible to cover this board with 1 x 3 tiles (horizontal and vertical) so that no two tiles overlap? Explain.

Problem 2:
Suppose you are given a set of 100 distinct positive integers. Show that there exist four integers { a, b, c, d } in this set such that a-b+c-d is a multiple of 2009.

Problem 3:
Show that for all positive integers n, we have
http://www.cise.ufl.edu/class/cot310...ks/Series1.bmp


Problem 4:
A suitcase contains 500 apples, 500 oranges, 500 peaches and 500 mangos. Every minute you choose one fruit from the suitcase. How long will it take to ensure that you have at least a dozen fruit of the same kind?

Problem 5:
Suppose there are (any) 5 points on a unit square (a square with area 1). Show that two of these points must be within http://www.cise.ufl.edu/class/cot310...meworks/rr.bmp of each other.

Problem 6:
Sixteen distinct integers are chosen between 1 and 30, inclusive. Show that you can always find a pair of integers (among these 16 integers you have chosen) such that their difference is 3.

~~~~~~~~~~~~~~~~~~~~~~~

#1 I think it's not possible, but unsure how to go about proving it
#2 I have no fucking clue
#3 I guess would just be math induction? Haven't tried it yet, hate doing induction with inequalities ~_~
#4 Easy, pigeonhole principle, 11*4+1=45 minutes. What I'm not sure is, is there a way to show this using the Ceiling(n/m) equation?
#5 Not sure how to go about this one
#6 Another pigeonhole problem, but no idea how to do this one lolz

Thanks for the help, anyone who decides to try and help. (Yeah, I'm fucked for this final lol)

[Dimmauk]

The answer is 42
http://www.supanet.com/media/00/04/93/deep_thought.jpg

[Norellicus]

Question 1 is just spatial relationships. Think about it and don't get trapped in the math, it's pretty obvious.

I'm not sure about others, I'm bad with irrational numbers

Edit: God damn, dimmauk wins, how did I miss that chance

[oldoldman]

3 can be done as an integral unless I'm missing something

∫n^-.5dn

which is (n^.5)/.5 or 2n^.5 which would make it equal, so I'm not sure why the say Less than

Problem 4 through logic and no math save arithmetic is 12 because it does not limit your choice options.

Not going to bother with the other ones.

Also my math must be flawed on the 3rd but I dunno why.

[Vade]

Heh, I took this class and then switched majors.

[Julian]

Heh, I took this class and then switched majors.

lol

[oldoldman]

What type of major is that class a req of?

[Julian]

What type of major is that class a req of?

I'm doing Computer Engineering, but there's a whole bunch of different majors taking this class.

[Korietsu]

I'm doing Computer Engineering, but there's a whole bunch of different majors taking this class.

Telcom/CE/SE/CS have to take it here

The square problem is simple. The largest distance between two points on a unit square is 2 root 2, due to Pythagoras' theorem.

The 3rd can probably done with Big O notation, and number two is a combanitorics problem.

[SDSD]

1) Break the problem up into the 4 border rectangles (area 1 X 6), and the inner square (area 6 X 6). I think the rest is straightforward

2) what a dick problem

3) Definitely induction. It doesn't look too hard, just tedious.

4) you got this.

5) Bisect the square diagonally. The longest possible distance between any two points is that line, i.e. points at two opposing corners. Then it's just geometry.

6) edit: I think you start with the fact that, you can select 15 possible integers s.t. all possible differences between pairs is some even number 2m. Then if you select one more number, it's obvious that there will be at least one pair with a difference of 3. The reasoning is obvious, I'm not sure how to write it formally. There aren't any proofs to this problem online sadly...I did find the assignment though.

[Qeomash]

There is a very specific reason I don't remember anything from my Discrete Mathematics course. Namely, I hated it.

[Kaylia]

Problem 1:
Consider a 7 x 7 checkerboard with the squares at the four corners removed (so that the remaining board has 45 squares). Is it possible to cover this board with 1 x 3 tiles (horizontal and vertical) so that no two tiles overlap? Explain.

I don't think it's possible.
No matter what pattern you start with, you're bound to get something that overlap. Not quite sure how to demonstrate it thought

Problem 2:
Suppose you are given a set of 100 distinct positive integers. Show that there exist four integers { a, b, c, d } in this set such that a-b+c-d is a multiple of 2009.

Is it really the question? Unless multiple mean something different in english, mutiple of 2009 are 4018, 6027...etc. If I give you {1,2,3...100} there is no way you can add the 4 number to reach a multiple of 2009.


Assuming those number are in sequence
If the 2009 is the multiple of the number you're looking for

ie: 7x287 = 2009


(a-b) + (c-d) = 7
(3) + (4) = 7
(N7-N4) + (N6-N2) = 7


I don't know...I guess i dont understand this question because it make little sense

Problem 3:
Show that for all positive integers n, we have
http://www.cise.ufl.edu/class/cot310...ks/Series1.bmp

Again..what the shit.
If n= 1
you have 1+many positive shit +1 <2

I dont see how it could converge since it will always be bigger than the geometric series 1+1/2+1/4 that converge to 2.

Problem 4:
A suitcase contains 500 apples, 500 oranges, 500 peaches and 500 mangos. Every minute you choose one fruit from the suitcase. How long will it take to ensure that you have at least a dozen fruit of the same kind?

0 minute? You have 41 dozen of each fruits in your suit case.

11*4+1 otherwise

Problem 5:
Suppose there are (any) 5 points on a unit square (a square with area 1). Show that two of these points must be within http://www.cise.ufl.edu/class/cot310...meworks/rr.bmp of each other.

4 corner, and 1 in the middle, followed with pythagora

d = sqrt( (1/2)²+(1/2)²)

Problem 6:
Sixteen distinct integers are chosen between 1 and 30, inclusive. Show that you can always find a pair of integers (among these 16 integers you have chosen) such that their difference is 3.

1-2-3-7-8-9-13-14-15-19-20-21-25-26-27 =15 integer, and its the worst case scenario. Adding one will necessarily add the possibility to get a difference of 3.

[Julian]

1) Break the problem up into the 4 border rectangles (area 1 X 6), and the inner square (area 6 X 6). I think the rest is straightforward

2) what a dick problem

3) Definitely induction. It doesn't look too hard, just tedious.

4) you got this.

5) Bisect the square diagonally. The longest possible distance between any two points is that line, i.e. points at two opposing corners. Then it's just geometry.

6) edit: I think you start with the fact that, you can select 15 possible integers s.t. all possible differences between pairs is some even number 2m. Then if you select one more number, it's obvious that there will be at least one pair with a difference of 3. The reasoning is obvious, I'm not sure how to write it formally. There aren't any proofs to this problem online sadly...I did find the assignment though.

Thanks a lot, this really helped. Except for #2, I pretty much understand all of them, just unsure of how I'd go about doing an actual proof on paper. Guy that grades it is a total asshole

[Quicklet]

@#3, I assume that n = the number of terms in the sequence,

so 1 < 2

1 + 1/root(2) < 2*root(2)

etc.

[Ramor]

the series 1/1 + 1/2 + 1/3 + ... 1/n (as n->infinity) is 2, so the rest should be easy to prove, though i don't think you'll have a problem there

the rest i'll try and do later when i'm not eating, not to mention it looks like there's a fair amount of decent answers already

[Kaylia]

@#3, I assume that n = the number of terms in the sequence,

so 1 < 2

1 + 1/root(2) < 2*root(2)

etc.

Stupid notation... should just write the sum.


Pretty easy to do then >_>

[edit]
More mistake..gdi. I hope no one saw that

[Norellicus]

1) Break the problem up into the 4 border rectangles (area 1 X 6), and the inner square (area 6 X 6). I think the rest is straightforward

This is incorrect, remember we're dealing with a square 7x7 board

[Trajan]

the series 1/1 + 1/2 + 1/3 + ... 1/n (as n->infinity) is 2, so the rest should be easy to prove, though i don't think you'll have a problem there

the rest i'll try and do later when i'm not eating, not to mention it looks like there's a fair amount of decent answers already

This isn't true... 1 + 1/2 + ... + 1/n = infinity, not 2.

[SDSD]

This is incorrect, remember we're dealing with a square 7x7 board

Oh fuck, I didn't remove enough squares. It gets way (edit: impossible) then...

The number of squares left uncovered in any arrangement is at least one.

[Teorem]

That doesn't look right. You shouldn't be able to reduce sum(k^-0.5, k: 1 to n) < 2n^0.5 to just sum(1/2n, n: 1 to n) < 1 quite like that...

I originally thought #1 would be a simple parity solution, but it doesn't work out correctly (because you can find a valid number of tiles satisfying the system of equations, just not a suitable arrangement). You should be able to use pigeonholing in an approach to solve it formally, but the right angle doesn't occur to me at the moment.

Edit: #2 looks like pigeonholing too, but I'm stumped on an approach because the initial number of pigeonholes exceeds the size of the initial set. I have to ask the same thing as someone else did earlier: was there a constraint on the original set of distinct integers?