Competition - post a photo you've taken of nature >>

The Proof is Trivial!

Scroll to see replies

The point is that the Riemann sum converges to the integral in the limit as

n \to \infty

, so the limit exists iff the integral exists.

Yes, of course. I think that things like this should be made clear, however, for the benefit of thick people like me. We have rights too, you know. I have a very good excuse for being super-dim tonight though so you'll have to let me off.

Reply 3641

Smaug123

Original post by atsruser

That was indeed what I intended :smile:

Reply 3642

Lord of the Flies

C'mon people, what has happened to this thread. Problem 570 from earlier requires two skills: knowing what a rectangle is, and knowing what an integer is.

Anyway, more!

Problem 577

Prove/disprove that there is a family

C_0,C_1,\dots

of disjoint subsets of the unit circle such that one can get from any member to any other through a rotation, and such that

\bigcup_n C_n

is the unit circle.

(this however is not trivial)

Reply 3643

Smaug123

Original post by Lord of the Flies

C'mon people, what has happened to this thread.

It's the exam holiday :P

Reply 3644

Smaug123

Original post by Lord of the Flies

The harder questions aren't gathering very much attention it seems, so here's a nice dinner-table problem!

Problem 570

If a rectangle can be subdivided into smaller rectangles, each having at least one side of integer length, must the initial rectangle also have at least one side of integer length?

I retract my answer, having been shown that it's nonsense :frown:

Spoiler

(edited 8 years ago)

Reply 3645

Lord of the Flies

Original post by Smaug123

...

Interesting approach :biggrin:

An alternative is the following:

Eliminate superfluous rectangles. Now colour in blue those with horizontal integer length and in red those with vertical integer length. Define a blue path as a chain of blue rectangles where the left edge of the next rectangle is aligned with right edge of the current one. Sim. for vertical path with top/bottom edges. If there is no blue path connecting the left & right sides of the big rectangle there must be a red path connecting the top & bottom.

(edited 8 years ago)

Reply 3646

Smaug123

Original post by Lord of the Flies

Interesting approach :biggrin:

An alternative is the following:

Eliminate superfluous rectangles. Now colour in blue those with horizontal integer length and in red those with vertical integer length. Define a path as a chain of adjacent rectangles of the same colour. If there is no red path connecting the top & bottom sides, there must be a blue path connecting the left & right sides, and vice versa.

Ugh, you disgusting combinatorialist. I gave the logician's answer :P

Reply 3647

username937760

Original post by Lord of the Flies

C_0,C_1,\dots

of disjoint subsets of the unit circle such that one can get from any member to any other through a rotation, and such that

\bigcup_n C_n

is the unit circle.

(this however is not trivial)

Assuming I am reading this correctly, this question feels like the same construction regarding the existence of a set which is not Lebesgue measurable.

Spoiler

Also, could you expand upon your solution to 570? I am not seeing why a chain of a single colour solves the problem.

Reply 3648

username1162972

Problem 578
Show that a graph is bipartite if and only if it contains no odd cycles.
A very nice problem.

Posted from TSR Mobile

Reply 3649

Renzhi10122

Original post by physicsmaths

Problem 578
Show that a graph is bipartite if and only if it contains no odd cycles.
A very nice problem.

Posted from TSR Mobile

Hmm, I wonder where you got that from :smile:

Reply 3650

username1162972

Original post by Renzhi10122

Hmm, I wonder where you got that from :smile:

Haha i actually like graph theory alot even though its combinatorics

(edited 8 years ago)

Reply 3651

poorform

Original post by physicsmaths

Problem 578
Show that a graph is bipartite if and only if it contains no odd cycles.
A very nice problem.

Posted from TSR Mobile

Proof:

\displaystyle \implies

: Suppose G is bipartite then there is two independent vertex sets A and B.

Now any edge in a walk in G must go from A to B (or B to A) hence for any cycle we will take an even number of steps so there can be no odd cycles in G.

\displaystyle \impliedby

: Let G be a graph with no odd cycles WLOG we may assume G is connected (since if G is not connected we can show that each connected part of G is bipartite and then the union of each part is also bipartite).

Pick a vertex

\displaystyle u \in V

. Define

\displaystyle A=\{u\} \cup \{v : d(u,v)=2m, m\in \mathbb{N}\}

and

Unparseable latex formula:

\displaystyle B=V\A

.

We claim that

\displaystyle V=A \cup B

and hence we have that G is in fact bipartite.

WLOG suppose there exists an edge

\displaystyle \{va\}

so that

\displaystyle v,a \in A

(of course we could suppose that they both are in B). Then

\displaystyle d(u,a),~d(u,v)

are both even.

\displaystyle d(a,b)

is the shortest path length between the two vertices.

Consider the shortest path from u to a:

\displaystyle P_{ua}

and similarly

\displaystyle P_{uv}

then consider the cycle

\displaystyle P_{ua}, \{av\}, P_{vu}

which has length

\displaystyle d(u,a)+d(v,u)+1

which is odd therefore we have a contradiction and no such edge may exist.

Hence G is bipartite.

\displaystyle ~~~\square

Problem 579: Let

\displaystyle G

be a graph with at least one edge show that

\displaystyle G

has at least

\displaystyle \chi (G) \choose 2

edges.

(edited 8 years ago)

Reply 3652

Lord of the Flies

Original post by DJMayes

Assuming I am reading this correctly, this question feels like the same construction regarding the existence of a set which is not Lebesgue measurable.

Yep bang on.

Also, could you expand upon your solution to 570? I am not seeing why a chain of a single colour solves the problem.

Bad use of the word adjacent, should be clearer now.

Reply 3653

atsruser

Original post by DJMayes

Assuming I am reading this correctly, this question feels like the same construction regarding the existence of a set which is not Lebesgue measurable.

Spoiler

This is the construction of the Vitali sets, isn't it? Or is there some difference?

Reply 3654

atsruser

Original post by Smaug123

That was indeed what I intended :smile:

I'm not sure what "that" is referring to here, but in a feeble attempt to add something of mathematical utility to this reply, I'll point out that I posted an easier problem of this type here: http://www.thestudentroom.co.uk/showpost.php?p=62174581&postcount=46 (still with no solution, so the glory and adulation that comes with solving a genuine Atsruser Problem^™ (accept no substitutes) is still up for grabs)

Reply 3655

username937760

Original post by Lord of the Flies

Yep bang on.

Bad use of the word adjacent, should be clearer now.

Yep, it's much clearer now, thanks!

Original post by atsruser

This is the construction of the Vitali sets, isn't it? Or is there some difference?

I believe so based on a quick Google - I didn't use the name because I hadn't heard it before.

Reply 3656

EnglishMuon

Probably a well known one but quite nice :smile:

Problem 580
Prove that the product of four consecutive integers cannot equal the product of two consecutive integers (Referring to

\mathbb{Z^{+}}

only).

Reply 3657

Renzhi10122

Original post by EnglishMuon

Probably a well known one but quite nice :smile:

Problem 580
Prove that the product of four consecutive integers cannot equal the product of two consecutive integers (Referring to

\mathbb{Z^{+}}

only).

Someone's been doing some BMO1 :smile:

Reply 3658

16Characters....

Problem 581*

You select a real number entirely at random from the interval

[0, 2\pi]

. What is the probability that

\sin x + \cos x

is greater than 1 in magnitude?

Disclaimer: I made this up myself. I think my logic is correct, but my probability is **** so if this is an impossible question (or significantly harder than the * I gave it) then my apologies.