1. H

    Pigeonhole principle question

    hello everybody, I`v got a little question on Pigeonhole principle: n people met at a party and some shook hands. prove that there are two people who shook hands in same number. thanks! Haim
  2. Y


    Prove that if I select 11 numbers from 1 to 20, then one number is multiple of other. I tried to get something done with the pigeonhole principle but did not have an idea of how to do so. What may help me see the problem more approachable?
  3. M

    Pigeonhole Principle

    Hello to all I am stuck with a question that goes like 410 letters are distributed in 50 apartments then which of the following are true S1 - Some apartment received atleast 9 letters S2 - Some apartment received atmost 8 letters S3 - Some apartment received atleast 10 letters S4 - Some...
  4. J


    How many integers from 100 through 999 must you pick in order to be sure that at least two of them have a digit in common? (they don't have to be in the same place value) worst case scenario involves picking integers such that none have had a digit in common the other questions I've had like...
  5. D

    Proving pigeonhole principle involving cardinality of finite sets

    Suppose A and B are finite sets and f:A→B. Prove that if |A|>|B|, then f is not one-to-one. Scratch work: Since the goal is in negation, I try to prove it by contradiction and assume that f is one-to-one. Since A has more elements than B, it can't be the case that f is one-to-one because some...
  6. I

    Combinatorics Pigeonhole problem

    Hello to all! So i have to do this problem: In the course of an year of 365 days Peter solves combinatorics problems. Each day he solves at least 1 problem, but no more than 500 for the year. Prove that for the year there exists an interval of consecutive days in which he had solved exactly...
  7. I-Think

    Squares and Pigeonhole Principle

    Let S be a square region of side length 2. Show that among any 9 points in the square, there are 3 which form a triangle of area \leq{\frac{1}{2}. I subdivided S into 8 triangles of equal area, \frac{1}{2}. Now I divide into 2 cases Case A: Where 3 points are in one triangle. Then the area of...
  8. Y

    Pigeonhole theorem problem

    Problem #1: Suppose N objects are distributed between B boxes in such a way that no box is empty. How many objects must we choose in order to be sure that we have chosen the entire contents of at least one box? My strategy was to find out the maximum number of contents one box can have, say M...
  9. B

    Proving A Division Property By Employing The Pigeon-Hole Pricinple

    Here is the problem: Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n. Here is the solution: Let a, a+1,...,a+n-1 be the integers in the sequence. The integers (a+i) \mod n, i=0,1,2...,n-1, are distinct because 0< (a+j)-(a+k)<n...
  10. S

    Pigeonhole problem

    I'm struggling with this problem for a while now, and I just can't figure it out. Prove: Let n_1, n_2, . . . , n_t \in N^+ . If n_1 + n_2 + . . . + n_t-t + 1 Objects are laid in t Pigeonholes then there's at least one i \in \{1, . . ., t\} so that the i-th pigeonhole has at least n_i objects in it
  11. B

    Pigeonhole Principle

    How is the PHP the same as saying that one of the numbers n1, n2, ... , nk is greater than or equal to their average?
  12. N

    PigeonHole Principle

    Show that in any set of n integers, n>= 3, there always exists a pair of integers whose di erence is divisible by n - 1. (Use the pigeonhole principle.) I can never seem to figure out how to do these pigionhole principle problems. Every one of them seems different to the last one I looked at...
  13. M

    application of pigeonhole principle

    It is given 13 integers c_1,c_2,...,c_{13} (some of them may be the same). Use pigeonhole principle to prove that there exist i and j with 0<i<j<=13 such that c_{i+1}+c_{i+2}+...+c_j is divisible by 13 for example, c_4+c_5+c_6+c_7 is divisible by 13. (Hint:consider the following 13 integers...
  14. M

    pigeonhole principle problem

    Hello! The following one is really bothering me: Suppose you live in a country with 9 000 000 inhabitants. At least how many people have their birthday on the same day? --------------------------------------- First I ignored the existence of the leap year, so I just simply computed 9 000...
  15. alexmahone

    Pigeon-hole Principle

    We chose n + 2 numbers from the set 1, 2, ..., 3n. Prove that there are always two among the chosen numbers whose difference is more than n but less than 2n.
  16. alexmahone

    Pigeon-hole Principle (3)

    One afternoon, a mathematics library had several visitors. A librarian noticed that it was impossible to find three visitors so that no two of them had met in the library that afternoon. Prove that then it was possible to find two moments of time that afternoon so that each visitor was in the...
  17. alexmahone

    Pigeon-hole Principle

    Let T be a triangle with angles of 30, 60 and 90 degrees whose hypotenuse is of length 1. We choose ten points inside T at random. Prove that there will be four points among them that can be covered by a half-circle of radius 0.42. My solution: Let us divide our triangle into three smaller...
  18. W

    A Pigeon-Hole Problem and an Irrational Root Problem

    I'm not sure what category these belong in. They're somewhat like puzzles. 3. A town has 2001 residents. Each resident has a non-negative amount of money (integer). If no two residents have the same amount of money and the combined sum of the balance of any 1000 residents is less than the...
  19. A

    pigeon-hole principle

    Statement 1 - If there are 'm' holes and 'n' pigeon's AND n>m then there is at least one hole with >1 pigeon Statement 2 - If there are 'm' holes and 'n' pigeon's AND n<m then there is at least one hole with 0 pigeon Are the above two statements equivalent? Sorry if this question is...
  20. J

    Pigeonhole Proof

    Prove that for any n+1 integers a1, a2, ..., a(n+1), there exist two of the integers ai and aj with i != j such that ai - aj is divisible by n. I know the use of the pigeonhole principle is the way to attack this proof. I just don't know how to show it. Any help is greatly appreciated. Thanks!