Discrete Mathematics!

[Ramor]

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

1/n^2 then? one of them is 2.

[Trajan]

1/n^2 then? one of them is 2.

That is equal to pi^2/6 (Basel problem that Euler solved). I think you are thinking about the sum from zero to infinity of 1/2^n.

On a side note, I am finding some of these problems very difficult, esp numbers 2 and 3. Must not give up until I solve them though... I hate finding problems I can't solve lol

[aurik]

#1: Prove that the top edge is VVH or HVV which is the same but mirrored. Then show that this top-edge pattern creates a plus-shaped gap in the center that cannot be filled.

#2: Holy shit, this one is hard. First, you can prove that the set can, WLOG, be considered to start at 1. Second, you show that any 2 number pairs have a unique difference (or else you can obtain 0 from a-b+c-d). Not sure where to go from there.

Also, 2009 = 41*49, and they're giving you 100 numbers = 50 pairs...?

#3:

#4: Show that, given that the condition has not been met, the chance to succeed with the next draw increases monotonically. Then, show that the chance to succeed on the 44th draw after 43 unsuccessful draws is not 100%, and the chance to succeed on the 45th draw after 44 unsuccessful draws is 100%.

#5:

#6: Assume the negative, and construct the set.

Rephrase the condition as: If n exists in the set, n+3 does not. For every number included in the set which is below 27, one number is excluded from the set. So a maximum of 13 numbers are included between 1 and 26.

If 27 is included, 28 and 29 must be included, as 30 is excluded and 3 of the 4 must be included. If 27 is excluded, 28 and 29 and 30 must be included, as 3 of the 4 must be included.

Therefore 25 and 26 are excluded, and we must construct a set of 13 numbers with this condition from the integers between 1 and 24.

Repeat this process (10 integers from 1..18, 7 integers from 1..12, 4 integers from 1..6, 1 integer from 1..0) to reach an eventual contradiction, thus the negative is false.

[Julian]

I found a pretty cool proof for the first one online, it basically drew a bunch of 1's, 2's, and 3's on the board, so that they would diagonally match, so it looks something like:

x12312x
1231231
2312312
3123123
1231231
2312312
X12312x

Kind of hard to see, but you can see how they match up diagonally. Anyway, any 3-piece horizontal or vertical tile that you try to make will use up a 1, 2, and 3. So if there's a solution, then there should be an equal number of 1's, 2's, and 3's. But there isn't. There's 16 1's, 16 2's, and 13 3's.

I have no idea how I would ever think of doing it like this lol

[Julian]

Alright, just finished the assignment. Thanks everyone who helped (*'-') I feel like I actually understand this stuff a little better now, too.

[DiscreetMaff]

The proof of this one is tricky, I had to do some research, and crack open my calculus book. Now, the series you have here is divergent, it is simply a p-series with p=1/2. I want to compare this series to a proven, convergent series. The geometric series:
1+1/2+1/4+1/8+1/16… +…1/2^n
You may know, is a popular convergent series, and converges to 2. ( There are many proofs of this series, I won’t bother proving it here)
Now, with the equation with p=1/2. Multiply both sides by 1/√n. The n term on the right side goes away and the right side becomes a constant, namely 2. Now, all the terms on the left side are multiplied by 1/√n. And by simply comparing the magnitudes of this sequence to those of the geometric sequence, you will see that the geometric terms are larger than the terms in the sequence to be proven. This simply implies that the sum of this sequence must be less than the sum of the geometric sequence, which converges to 2. Therefore the sum of this sequence must also be less than 2, proving the inequality to be true. This makes sense because as n becomes larger, you will add more terms, but the magnitude of each term will also decrease in proportion.

mappytacks

[Suiram]

The thing is, since it's a discrete mathematics course, I doubt that he was supposed to use any sort of Analysis like convergent series or integrals like someone was talking about earlier. It seemed to me when I glanced at it last night that there should be some obvious inequality that can be used to show that 1/sqrt(n) < 2 (sqrt(n) - sqrt(n-1)) for a straightforward inductive proof, although I guess not obvious enough since I'm still not sure what it would be.

#2 has been bothering me a bit. My instincts make me think you're supposed to show that given 100 numbers between 0 and 2008, there must be two distinct pairs with the same sum, but maybe that's the wrong approach.

[Suiram]

Oh, I think I got it actually (the obvious inequality for #3, #2 still eludes me). It's okay to post the full thing since the assignment is already done? I'll spoiler it just in case.

Spoiler: show

√(n-1)/√(n) < 1
1 + √(n-1)/√(n) < 2
(√(n) + √(n-1))/√(n) < 2 * (n - (n - 1))
(√(n) + √(n-1))/√(n) < 2 * ((√(n) + √(n-1)) * (√(n) - √(n-1)))
1/√(n) < 2 * (√(n) - √(n-1))

That's for the inductive step of the proof. Forgive me if I made an error on this, I haven't had all my coffee. Either way I was expecting something like this to be the answer.

[DiscreetMaff]

You are true, this is a Discreet Maff course but out professor doesnt' really care as long you you prove it in some way. Of course the obvious method was to use mathematical induction but I'm sure that is also fine because it does use logic to an extent

[Teorem]

Now, the series you have here is divergent, it is simply a p-series with p=1/2. I want to compare this series to a proven, convergent series. The geometric series:
1+1/2+1/4+1/8+1/16… +…1/2^n...

This simply implies that the sum of this sequence must be less than the sum of the geometric sequence, which converges to 2. Therefore the sum of this sequence must also be less than 2, proving the inequality to be true. This makes sense because as n becomes larger, you will add more terms, but the magnitude of each term will also decrease in proportion.

The problem is that the series is a divergent p-series, and unless I'm forgetting something key, its sum is unlimited and certainly not upper-bounded by a series that converges to 2.

(√(n) + √(n-1))/√(n) < 2 * (n - (n - 1)

I'm curious how you jumped to this step in your induction since (n-(n-1)) isn't 1 and the term isn't applied to both halves of the inequality.

To the OP: Do you think you'll get an answer sheet to these review questions? I'd like to see what the answers were supposed to be to the non-obvious ones, having spent way too much time on trying to solve them than I really should have.

[aurik]

#2 has been bothering me a bit. My instincts make me think you're supposed to show that given 100 numbers between 0 and 2008, there must be two distinct pairs with the same sum, but maybe that's the wrong approach.

Nothing in the question said that the numbers are between 0 and 2009

[Julian]

To the OP: Do you think you'll get an answer sheet to these review questions? I'd like to see what the answers were supposed to be to the non-obvious ones, having spent way too much time on trying to solve them than I really should have.

Nope

Prof is an asshole, and it really wouldn't surprise me if there were any mistakes in any of those questions.

(He spent an entire day calling pigeonhole piegonhole, without noticing it.)

[Suiram]

I'm curious how you jumped to this step in your induction since (n-(n-1)) isn't 1

It isn't? I forgot to put a parenthesis at the end, but what I meant, and what you wrote, equals 1.

Nothing in the question said that the numbers are between 0 and 2009

But it resolves to one. The difference between two numbers (in this case "a+c" and "b+d") is divisible by 2009 iff they both yield the same remainder upon division by 2009. This transforms the problem from one about all positive integers into one about the numbers between 0 and 2008. Then when you look at the number of possible sums of 100 numbers (n1 + n2, n1 + n3, ..., n1 + n100, n2 + n3, ...) you get 4950 sums*, so by the pigeonhole principle (or Dirichlet principle or whatever you want to call it), two sums must have the same remainder, and the rest follows easily.

*Edit: This isn't quite the right application, because 4950 doesn't take into account that you can't use the same number twice, but it's the same idea. Either find the right number by taking away repeated numbers, or change it into a question about sums of remainders first (where repetition could be allowed).

[Teorem]

It isn't? I forgot to put a parenthesis at the end, but what I meant, and what you wrote, equals 1.

You're right, it was 1. I'm tired and thinking and typing two different things.

The problem I was having with #2 is that you effectively have 1005 pigeonholes ({0}, {1, 2008}, etc.) based on the remainders of each distinct integer % 2009 when you start off with something like proving (a+b|2009). The additional subtractions throw me off though, as well as the fact that you're only picking some random 100 distinct integers over a substantially larger number of holes unless you're able to reduce them by an order of magnitude somehow.

I also don't see how you can pick 1 as the start without loss of generality, because 1 isn't assured to be one of the values, or even the result of a-b+c-d.

Nope

Prof is an asshole, and it really wouldn't surprise me if there were any mistakes in any of those questions.

What a dick, I want to know the (right) answers.

[Suiram]

This is what I was trying to say about #2. You've got 4950 unordered pairs of integers from your set of 100. Each of those pairs corresponds to a number, r, which is the remainder obtained after dividing the sum of the members of a pair by 2009 (i.e. if your pair is {5000, 250}, then r=1232). If any two such pairs, {a, c} and {b, d}, have the same r, then you're done, since then a-b+c-d is divisible by 2009. There are only 2009 r's (0 through 2008). Only part I'm not sure about yet is how to go about demonstrating that you have too many pairs for that not to happen, since you have to account for the fact that none of your pairs can have overlapping constituents.

[aurik]

Suiram: ooh, clever use of modulo to restrict the number set to [1, 2009]


Teorem
You can choose 1 as the lowest number in the set without loss of generality.

You can write the set as s + {n0, n1, n2, n3 ...}, where nX is strictly increasing with X.

The property we are examining is F(a,b,c,d) = a+c-b-d = (s+nA) + (s+nC) - (s+nB) - (s+nC) = nA + nC - nB - nD.

If we choose the same indices a,b,c,d on the set {n0, n1, n2, n3 ...}, F(a,b,c,d) on this set is nA+nC-nB-nD. Therefore F(a,b,c,d) on the set {n0,n1,n2,n3...} has the same range as s + {n0,n1,n2,n3...}.

Thus, the range of F() for s + {n0,n1,n2,n3 ...} where s is chosen such that n0 = 1 is the same as the range of F() for {n0, n1, n2, n3 ...}. n0 is 1, so WLOG we can always choose the set such that the lowest number is 1.

[Julian]

Got a new question!

Was looking through old exams, studying for final, and there is this one pigeonhole problem which I just don't get.

Let x be an irrational number. Show that for some positive integer j not exceeding 6, the absolute value of the difference between jx and the nearest integer to jx is less than 1/6.

Part 2: Use the above to explain why it is possible to approximate the irrational number e = 2.71828blahblah... using a rational number of the form p/q (where 0 < q < 7) with error less than 1/6, |e-(p/q)| < 1/6

[Julian]

Also got my grade for the extra credit.. 80%? Out of 4 questions? sigh

[Anomander]

Oh man, Discrete math...bleh. Took this my sophomore year of college during CS, and now in my Senior year I can not remember how to do half this shit. Somehow pulled a B in that class. Something I found funny, our school had such a high drop out rate from this class that they split it into two courses the year after I took it.

Good luck on your final, sorry I didn't stop in earlier and throw in my two cents, I still have my book and many of the assignments lieing around.

[Suiram]

I got #2 fully worked out earlier, I'm not sure that it even matters anymore, but in case anyone is still curious. This is along the method I was talking about before, there's probably a more straight-forward approach but this gets the job done.

Let S be the set of all two element subsets of your set of 100 integers. So S has 4950 members. For all r between 0 and 2008, let S(r) ⊆ S be the set of all pairs whose sum is congruent to r modulo 2009. Note that if {a,c} ∈ S(r) and {b,d} ∈ S(r) for some r, where a, b, c, and d are all distinct integers, then a-b+c-d is congruent to 0 mod 2009, and so is divisible by 2009.

So, suppose for contradiction that for every r, the intersection of any two members of S(r) is non-empty. (That is, any two pairs of numbers whose respective sums yield the same remainder have a common element). This breaks the problem into two subcases:

Case 1, There is an S(r) with four or more members:
Observe that if S(r) contains greater than three members, then each constituent pair must have the same common element. Call that element, k. (Does this require further justification? There are two ways to construct a three-element subset of S, one where each pair contains a common element, and one where the third pair contains the two elements not common to the first two. But this second way cannot be extended to include a fourth element without violating our assumption that the intersection of each pair is non-empty). Choose four members of S(r): {k,a}, {k,b}, {k,c}, and {k,d}. Observe that since k+a ≡ k+b ≡ k+c ≡ k+d (mod 2009), then a ≡ b ≡ c ≡ d (mod 2009), and so a-b+c-d ≡ 0 (mod 2009).

Case 2, for all r, S(r) contains at most 3 members:
As there are 4950 pairs, and 2009 subsets of S, notice that there must be at least 932 subsets that contain 3 pairs. Pick one, call it S(r1), and consider two distinct elements with common element, k: {k,a} and {k,b}. Now, since there are 294 pairs in S containing either k, a, or b, and at least 932 subsets of S of size 3, let S(r2) be such that it contains 3 pairs, with none of its members containing k, a, or b. Choose any two elements from S(r2), with a common element, l: {l,c} and {l,d}. Now, since k+a ≡ k+b (mod 2009), a ≡ b (mod 2009), and so a-b ≡ 0 (mod 2009). Likewise, c-d ≡ 0 (mod 2009). So a-b+c-d ≡ 0+0 ≡ 0 (mod 2009).


(I used modular arithmetic above because it made it more concise, and my understanding is that most Discrete Mathematics classes will touch on it. If not though, it could be translated into equivalent statements about remainders.)