Scribd Logo
Upload

Welcome to Scribd!

  • 33 views

    Ex Set 4

    Uploaded by

    Juan Robinson
    (1) The document provides 5 exercises related to the pigeonhole principle and counting problems. It asks to determine how long it will take to pick 12 of the same fruit from a sack of 400 total fruits picked randomly each minute. (2) It also includes 3 exercises on partially ordered sets (posets). It asks to draw Hasse diagrams for all 3-element and 4-element posets and prove properties about relations on posets and order-preserving maps between posets. (3) The final exercise asks to show that the inverse of an order-preserving bijection between finite posets is also order-preserving.

    Copyright:

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

    Ex Set 4

    Uploaded by

    Juan Robinson
    33 views2 pages
    (1) The document provides 5 exercises related to the pigeonhole principle and counting problems. It asks to determine how long it will take to pick 12 of the same fruit from a sack of 400 total fruits picked randomly each minute. (2) It also includes 3 exercises on partially ordered sets (posets). It asks to draw Hasse diagrams for all 3-element and 4-element posets and prove properties about relations on posets and order-preserving maps between posets. (3) The final exercise asks to show that the inverse of an order-preserving bijection between finite posets is also order-preserving.

    Original Description:

    An excellent problem set on Combinatorics

    Original Title

    ExSet4

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    (1) The document provides 5 exercises related to the pigeonhole principle and counting problems. It asks to determine how long it will take to pick 12 of the same fruit from a sack of 400 total fruits picked randomly each minute. (2) It also includes 3 exercises on partially ordered sets (posets). It asks to draw Hasse diagrams for all 3-element and 4-element posets and prove properties about relations on posets and order-preserving maps between posets. (3) The final exercise asks to show that the inverse of an order-preserving bijection between finite posets is also order-preserving.

    Copyright:

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

    Ex Set 4

    Uploaded by

    Juan Robinson
    (1) The document provides 5 exercises related to the pigeonhole principle and counting problems. It asks to determine how long it will take to pick 12 of the same fruit from a sack of 400 total fruits picked randomly each minute. (2) It also includes 3 exercises on partially ordered sets (posets). It asks to draw Hasse diagrams for all 3-element and 4-element posets and prove properties about relations on posets and order-preserving maps between posets. (3) The final exercise asks to show that the inverse of an order-preserving bijection between finite posets is also order-preserving.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    EXERCISE SET 4

    1. Pigeonhole Principle
    (1) A sack contains 100 mangoes, 100 mosambis, 100 bananas, and
    100 apples. If we pick one fruit out of this sack every minute,
    how long will it be before we are assured of having picked at
    least 12 pieces of any one of the four mentioned fruits?

    (2) Show that in a group of n > 1 people, there are two have the
    same number of acquaintances (it is assumed that no person is
    acquainted with him/herself).

    (3) Prove that of any five points chosen within a square √ of side
    length 2, there are two whose distance apart is atmost 2.

    (4) Let S be a set of six points on a plane, with no three of the


    points collinear. Colour the the 15 line segments determined by
    the points of S, either red or blue. Show that there are atleast 2
    monochromatic triangles (either 2 red traingles, 2 blue triangle,
    or 1 red and 1 blue triangle). Note that we already know, at
    least one monochromatic triangle exists.

    (5) The 45 = 10
    
    2
    line segments joining 10 points are arbitrarily
    coloured red or blue. Show that there must exist three points
    such that they form a red triangle, or 4 points, such that the six
    line segments joining them are blue (show that r(3, 4) ≤ 10).
    2. Partially Ordered Sets
    (1) Draw Hasse diagrams of all the three-element posets, and of all
    the four element posets.
    (2) A preposet (or quasi-ordered set) is a set P with a binary rela-
    tion ≤ such that it is reflexive and transitive, but not necessairly
    anti-symmetric. We define a relation ∼ on P as follows: For
    s, t ∈ P
    s ∼ t ⇔ (s ≤ t and t ≤ s).
    Show that ∼ is an equivalence relation.
    Date: 12 August 2018.
    1
    2 EXERCISE SET 4

    (a) Denote by P̃ denote the equivalence classes under ∼. For


    S, T ∈ P̃ , define S ≤ T if
    ∃ s ∈ S, t ∈ T such that s ≤ t in P.
    Then show that this ≤ makes P̃ a poset.
    (b) Let Q be a poset. Let f : P → Q be an order-preserving
    map. Let r : P → P̃ be the map that sends s ∈ P to
    that S ∈ P̃ such that s ∈ S. Show that there is a unique
    order-preserving map g : P̃ → Q such that f = g ◦ r

    f Q
    P
    r g
    P̃

    (3) Let P be a finite poset. Let f : P → P be an order-preserving


    bijection. Show that f −1 is order-preserving.
    (Note that in the definition of isomorphism, it was explicitly
    mentioned that f −1 has to also be order-preserving).

    You might also like