Hey there! Sign in to join this conversationNew here? Join for free
    Offline

    11
    ReputationRep:
    (Original post by joostan)
    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.
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by atsruser)
    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.
    That was indeed what I intended
    Offline

    18
    ReputationRep:
    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)
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by Lord of the Flies)
    C'mon people, what has happened to this thread.
    It's the exam holiday :P
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (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
    Spoiler:
    Show

    It can't be done. Say a rectangle has a *good* subdivision if it has the subdivision you require. Let R be a rectangle with non-integer sides, which has a good subdivision; let R be minimal (in perimeter) with this property.

    I'll do this in large stages, but the first claim is not necessary.

    Claim: if the top-left sub-rectangle in a good subdivision is integer-by-integer, then we can find a smaller main-rectangle with non-integer side lengths which has a good subdivision. (And hence a contradiction.)
    Proof: slice the main rectangle completely along the two internal edges of the top-left sub-rectangle, keeping only the bottom-right chunk (the "complement". The complement has non-integer side lengths, and the subdivision from R inherits to a good subdivision on the complement, since we only ever chop off integer lengths from any sub-rectangle.

    So suppose the top-left sub-rectangle S has integer height only. Chop in the width-direction along the bottom edge of S, making the "height-complement". We've lost an integer height from every sub-rectangle, so the complement now has a good (inherited) subdivision but is smaller: a contradiction.

    If S has integer width only, then we can chop in the height-direction instead for the same effect.
    Offline

    18
    ReputationRep:
    (Original post by Smaug123)
    ...
    Interesting approach

    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.
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by Lord of the Flies)
    Interesting approach

    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
    Offline

    16
    ReputationRep:
    (Original post by 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)
    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:
    Show


    Define an equivalence relation by  a \equiv b \iff b-a \in \mathbb{Q}

    Define a set  C_0 by choosing a member of each equivalence class by the Axiom of Choice; then enumerate  \mathbb{Q} \cap [0,1] and define  C_i = C_0 +q_i \ \mod(1) . Each of these can be attained from another by translation, so corresponding points on the unit circle can be attained by rotation.



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

    18
    ReputationRep:
    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
    Offline

    8
    ReputationRep:
    (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
    Offline

    18
    ReputationRep:
    (Original post by Renzhi10122)
    Hmm, I wonder where you got that from
    Haha i actually like graph theory alot even though its combinatorics
    Offline

    9
    ReputationRep:
    (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 \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.
    Offline

    18
    ReputationRep:
    (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.
    Offline

    11
    ReputationRep:
    (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:
    Show


    Define an equivalence relation by  a \equiv b \iff b-a \in \mathbb{Q}

    Define a set  C_0 by choosing a member of each equivalence class by the Axiom of Choice; then enumerate  \mathbb{Q} \cap [0,1] and define  C_i = C_0 +q_i \ \mod(1) . Each of these can be attained from another by translation, so corresponding points on the unit circle can be attained by rotation.

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

    11
    ReputationRep:
    (Original post by Smaug123)
    That was indeed what I intended
    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/show...1&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)
    Offline

    16
    ReputationRep:
    (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.
    Offline

    14
    ReputationRep:
    Probably a well known one but quite nice

    Problem 580
    Prove that the product of four consecutive integers cannot equal the product of two consecutive integers (Referring to  \mathbb{Z^{+}} only).
    Offline

    8
    ReputationRep:
    (Original post by EnglishMuon)
    Probably a well known one but quite nice

    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
    Offline

    10
    ReputationRep:
    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.
    Offline

    11
    ReputationRep:
    (Original post by EnglishMuon)
    Probably a well known one but quite nice

    Problem 580
    Prove that the product of four consecutive integers cannot equal the product of two consecutive integers (Referring to  \mathbb{Z^{+}} only).
    Solution 580:
    Spoiler:
    Show
    Suppose for a contradiction that:
    n(n+1)(n+2)(n+3)=k(k+1) for k,n \in \mathbb{N}.
    Then: LHS=(n^2+3n)(n^2+3n+2)=(n^2+3n)^  2+2(n^2+3n)=(n^2+3n+1)^2-1.
    \implies n(n+1)(n+2)(n+3)+1=m^2 for m \in \mathbb{N}.
    \iff m^2=k(k+1)+1=k^2+k+1.
    But now we see that we require k^2<m^2<(k+1)^2.
    A contradiction, as k,m \in \mathbb{N}.
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Would you like to hibernate through the winter months?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.