TT's Maths Thread

[/0]

Ah true... I felt something was fishy
It's like how the redundant condition in metric spaces can be derived from the triangle inequality

[Ahmad]

It's not true, it's tricky and there is something wrong with it. 

[zzdfa]

What's wrong with this logic?

I claim that a symmetric and transitive relation is also reflexive.

Let a be in X, and let b be in X such that a ~ b. Now being symmetric means b ~ a also, and transitivity implies a ~ a as required.

sneaky

this talk about equivalence relations reminds me of a nice alternate definition of an equivalence relation:

a relation ~ is called an equivalence relation if and only if there exists a function f such that



(verify that it is indeed equivalent to the usual definition)

[TrueTears]

Oh right, thanks guys, I proved it now.


Another question: Show that if we select 151 distinct computer science courses numbered between 1 and 300 inclusive then at least 2 are consecutively numbered.

I know pigeonhole theorem is involved but how do I apply it?

[brightsky]

Pigeons: 151 pigeons defined by the selected distinct computer science courses.
Holes: 150 holes are defined by {1, 2} , {3,4}, {5,6} ... {299,300}

Since 151 = 150 *1 + 1, then by the pigeon hole principle, at least one hole will have 2 pigeons in it, no matter how which numbers you select.

[TrueTears]

AWESOME, THANK YOU VERY MUCH!!


Actually wait, if you have {1,2}, {3,4} which means each computer science course can have 2 numbers assigned to it, doesn't that mean the 151th computer science course will have no numbers assigned to it?

Eg, let the computer science courses be c1, c2, c3 ... c151

c1 = {1,2}

c2 = {3,4}

.
.
.

c150 = {299,300}

c151 = ?

[pooshwaltzer]

There seems to be a number of mutual exclusivities at play here...No course overlapping apparently...and it's a permutations rather than combinatorics sequence since ascension of order is a requirement.

Come to think of it...

{1, 2} , {3, 4}, {5, 6} ... {299, 300} = 150 distinct non-overlapping pairs ONLY

{1, 2}, {2, 3} , {3,4}, {4, 5} ... {299, 300} = 299 distinct overlapping & non-overlapping pairs

299 - 150 = 149 distinct overlapping pairs ONLY

[TrueTears]

ok, so how do i do the q?

i am still a bit confused...

[brightsky]

Hmm..not entirely sure what you mean, but imagine the 151 selected computer science courses as pigeons. There are 300 choices, and for the sake of highlighting there must be a consecutive pair, we group the 300 choices as {1, 2}, {3, 4} ... In an extreme case, we would choose the computer course 1, 3, 5, 7, 9, ... , 299 as the first 150 of the selected courses, but the 151st one must be either 2, 4, 6, 7, 8, etc etc, so there must be at least 2 that are consecutively numbered.

Example of a selection:

1, 2 , 3, 5, 7, 9, ..., 299 - then the consecutively numbered pairs would be 1, 2 and 2, 3.


The {1, 2}, {3, 4}...{299, 300} are not computer courses, rather pigeon-holes that we have constructed to make the problem easier to solve/understand.

[TrueTears]

wait so does that mean that all the numbers from 1 to 300 inclusive doesn't have to be used?

Coz I interpreted when the question said

we select 151 distinct computer science courses numbered between 1 and 300 inclusive

That all 300 numbers (1,2,3...300) must be used so some computer courses will have 2 or more numbers assigned to it.

[brightsky]

Nup, we are selected 151 courses FROM the 300 courses given. The courses are named 1, 2, 3, 4, 5, ..., 300, so if we randomly pick 151 courses from that, we will get consecutive pairs.

[TrueTears]

Yeah, so we have 300 course numbers (pigeons) and we have to assign them to 151 computer courses (pigeonholes) so we will get at least 2 pigeons in 1 pigeonhole, in other words, 2 course numbers for 1 computer course.

Sorry I'm a bit slow at pigeonhole theorem, was never good at it.

[/0]

It might be clearer to try by contradiction:

Suppose there exists a list of 151 integers in the interval [1,300] in which all consecutive integers differ by at least 2.

(The "at least 2" can be changed to just "2": We aim to show that not all integers can differ by 2, and as a consequence they obviously can't differ by 3, since that would make the list occupy an even larger interval.)

But the "smallest" such list of numbers would be {1,3,5,7,9,...,301}, or {-1,1,3,5,...,299} and this cannot be contained in the interval [1,300].

So out of the 151 integers in [1,300] there must exist at least 1 pair of integers in which differ by less than 2. (taking the negation of the 'false' hypothesis at the start)

[brightsky]

Yeah, so we have 300 course numbers (pigeons) and we have to assign them to 151 computer courses (pigeonholes) so we will get at least 2 pigeons in 1 pigeonhole, in other words, 2 course numbers for 1 computer course.

Sorry I'm a bit slow at pigeonhole theorem, was never good at it.

The pigeons are the 151 selected numbers. We are assigning the pigeons to pigeonholes constructed from the 300 courses to choose from.

This can be proved by way of pure logic. We have 151 courses to choose out of the 300 available courses. Of course there will be at least 2 pairs that are next to each other. Pigeon hole principle essentially looks at the worst case scenario, so if we were, for the first 150 selections, to avoid the consecutive pairings, then we have two choices, either to select 2, 4, 6, 8, 10, 12, ..., 300 or 1, 3, 5, 7, 9, ..., 299. In either case, we have only considered the first 150 selections. The 151st has to be one of the numbers remaining, and no matter what 151st number we pick, we will then get two numbers next to it, for example 1, 3, 5, 7, 9, 11, 12 , 13, 15, ... 299, etc. The 151st is FORCED into a position that mandates at least 2 consecutive pairings.

[TrueTears]

I see, that makes perfect sense, so there must be a fallacy in my logic in the my statement above, can you show me how?

Thanks heaps btw!