Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 35 views

    Extremal Principle: Liming Sun

    Uploaded by

    Dalia Yesmin
    This document contains two sections. The first section provides an introduction and examples of using extremal principles to solve problems. The second section lists practice problems related to extremal principles in geometry, number theory, and graph theory. The problems range in difficulty from 1 to 3 and reference additional text for more information.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Extremal Principle: Liming Sun

    Uploaded by

    Dalia Yesmin
    35 views2 pages
    This document contains two sections. The first section provides an introduction and examples of using extremal principles to solve problems. The second section lists practice problems related to extremal principles in geometry, number theory, and graph theory. The problems range in difficulty from 1 to 3 and reference additional text for more information.

    Original Description:

    Original Title

    Extremal_Principle

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains two sections. The first section provides an introduction and examples of using extremal principles to solve problems. The second section lists practice problems related to extremal principles in geometry, number theory, and graph theory. The problems range in difficulty from 1 to 3 and reference additional text for more information.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    35 views2 pages

    Extremal Principle: Liming Sun

    Uploaded by

    Dalia Yesmin
    This document contains two sections. The first section provides an introduction and examples of using extremal principles to solve problems. The second section lists practice problems related to extremal principles in geometry, number theory, and graph theory. The problems range in difficulty from 1 to 3 and reference additional text for more information.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Extremal Principle

    Liming Sun

    A mathematician is a device for turning coffee into theorems


    −Alfréd Rényi

    1 Introduction
    The existing order on a set can be found useful when on is trying to solve a problem. An order on a finite
    set has maximal and minimal elements. If the order is total, the maximal element is unique. Quite often it
    is useful to look at such extremal elements.
    Example: At a party assume that no boy dances with all the girls, but each girl dances with at least
    one boy. Prove that there are two girl–boy couples gb and g 0 b0 who dance, whereas b does not dance with
    g 0 , and g does not dance with b0 .
    Example: Find all odd positive integers n greater than 1 such that for any coprime divisors a and b of
    n, the number a + b − 1 is also a divisor of n. [2]
    Example: Suppose you are sitting at a perfectly round table with an adversary about to play a game.
    Next to each of you is an infinitely large bag of pennies. The goal of the game is to be the player who is able
    to put the last penny on the table. Pennies cannot be moved once placed and cannot be stacked on top of
    each other; also, players place 1 penny per turn. There is a strategy to win this game every time. Do you
    move first or second, and what is your strategy?

    2 Practise Problems
    2.1 Part I
    √
    1. n 2 is not an integer for any positive integer n. ([1])
    2. Prove that among any 50 distinct positive integers strictly less than 100 there are two that are coprime.
    ([2])
    π
    3. Given n ≥ 3 points in the plane, prove that some three of them form an angle less than or equal to n.
    [2]
    4. Given a finite number of points in the plane, not all colinear, prove there is a straight line which passes
    through exactly two of them. [3].
    5. A cube can not be divided in to several pairwise distinct cubes. [1].

    2.2 Part II
    1. Consider a planar region of area 9, obtained as the union of finitely many disks. Prove that from these
    disks we can select some that are mutually disjoint and have total area at least 1.

    2. Prove that among any eight positive integers less than 2004 there are four, say a, b, c, and d, such
    that([2])
    4 + d ≤ a + b + c ≤ 4d

    1
    3. Let a1 , a2 , · · · , an , · · · be a sequence of distinct positive integers. Prove that for any positive integer n
    ([2]),
    2n + 1
    a21 + a22 + · · · + a2n ≥ (a1 + · · · + an ).
    3
    4. Let X be a subset of the positive integers with the property that the sum of any two not necessarily
    distinct elements in X is again in X. Suppose that {a1 , a2 , ..., an } is the set of all positive integers not
    in X. Prove that a1 + a2 + · · · + an ≤ n2 . [2]
    5. Complete the square in the following Figure with integers between 1 and 9 such that the sum of the
    numbers in each row, column, and diagonal is as indicated. [2]

    6. Given n points in the plane, no three of which are collinear, show that there exists a closed polygonal
    line with no self-intersections having these points as vertices. [2]
    7. Show that any polygon in the plane has a vertex, and a side not containing that vertex, such that the
    projection of the vertex onto the side lies in the interior of the side or at one of its endpoints. [2]
    8. In some country all roads between cities are one-way and such that once you leave a city you cannot
    return to it again. Prove that there exists a city into which all roads enter and a city from which all
    roads exit. [2]
    9. Suppose that n(r) denotes the number of points with integer coordinates on a circle of radius r > 1.
    Prove that ([2])
    3
    n(r) < 2πr 2 .

    References
    [1] Arthur. Engel. Problem-solving strategies. Springer, 1998.
    [2] Razvan Gelca and Titu Andreescu. Putnam and beyond. Springer, 2007.
    [3] Loren C. Larson. Problem-solving through problems. Springer-Verlag, 1983.

    You might also like