pigeon

  1. J

    Pigeon Hole Principle - proof of d as a positive integer

    Let d be a positive integer and consider any set A of d+1 positive integers. Show that there exists two different numbers x,y ϵ A so that x mod d = y mod d and x=/=y. I know I have to use the pigeon hole principle but I'm having trouble with it still. Help would be great.
  2. S

    pigeon hole principle

    What is pigeon hole principle ? using these principle show that in any group of 36 people, we can always find 6 people who were born on the same day of week. please help somebody please help
  3. E

    Pigeon hole principle

    I understand what the pigeonhole principle is. if there are n pigeons and m holes than at least one hole has more than n/m pigeons. But how do I show it with specific example? a.Suppose a programmer wrote 1000 lines of code in 30 days. Show that there must be at least one day when the...
  4. J

    Pigeon Hole Principle

    Show that given 52 integers there are two of them whose sum or difference is divisible by 100. Can someone show this using the pigeon hole principle please. Thanks!!
  5. F

    Pigeon Hole Proof

    On a homework assignment I was given the following: How many functions are there from {1,...,n} to {1,...,n} that are not 1-to-1? I immediately thought the answer to this question was zero. I tried proving this with the pigeon hole principal. I said let there be n boxes and let there be n...
  6. oldguynewstudent

    Pigeon hole principle for odd or even product

    Let n be odd and suppose (x_{1},x_{2},\ldots,x_{n}) is any permutation of [n]. Prove that the product (x_{1}-1)(x_{2}-2)\cdots(x_{n}-n) is even. Is the result necessarily true if n is even? Give a proof or counterexample. If the x_{i}'s are written in ascending order, then each is paired with...
  7. I

    Pigeon Hole Principle

    Alright, here is my problem: 30 buses are to be used to transport 2000 refugees from Location A to Location B. Each bus has 80 seats. Assume one seat per passenger. Prove that one of the buses will have at least 14 empty seats. Now.. \frac{2000}{80}=25 which means we wont need to use the 30...
  8. B

    [SOLVED] pigeon hole principle

    Can anybody help me out with this one? There are 8 different courses available, and each student must choose 5 courses to put in his/her plan of studies. What is the minimum number of students such that, no matter what they choose, there will be at least 10 studentws with the same plan? Is...
  9. D

    Pigeon Holes Question

    I am stuck on this question involving the pigeon hole principle. Any help is appreciated. In a gathering of 30 people, there are 104 different pairs of people who know each other. a. Show that some person must have at least seven acquaintances. b. Show that some person must have fewer than seven...
  10. W

    Pigeon Hole principle

    Hey Im having a hard time on how to start with this problem. Any help would be appreciated. This is actually a 4 part problem. John has to visit n apartments to get candies frome each. There is no particular order in which he is going to visit those apartments. A) In how many ways can he...
  11. W

    Pigeon Hole Principle

    I'm pretty sure that I should apply the pigeon hole principle, but I'm not sure exactly how. Let a_i with i ranging from 1 through n be a sequence of integers (both positive and negative, not necessarily all different). Prove that there exists integers j and k with 1 <= j <= k <= n such that...
  12. J

    the pigeon hole principle

    it is know that among any group of 3 students in a class 2 of them are friends. the total number of students is 25. prove that there is a student who has at least 12 friends. thnx justanotherperson
  13. P

    Pigeon Hole Principle

    A professor teaching a Mathematics course gives a multiple choice quiz that has 10 questions,each with four possible answers.What is the minimum number of students that must be in the professor's class in order to guarantee that at least 3 paper sheets are identical? (Assume that no answers are...
  14. F

    Pigeon Hole Principle Question

    Utilizing the pigeon hole principle answer the following question: show that if any 9 digit integers are chosen from 1 to 16, then two of them will add up to 17
  15. T

    Discrete Math, Pigeon Hole Principle/Sum of Elements of Subsets

    Ok, so the question is to show for any set A of positive integers taken from {1,2,...,12}, A must contain two disjoint subsets whose elements when added up give the same sum. Now, reading around on this site, what I have so far is that there are 2^6 possible subsets of a 6-element set, and the...
  16. E

    Pigeon hole principle

    I have problem with this questions: How many different 5-element subsets can be formed from the set {1,2,3,4,5,6,7,8,9}? Two elements of the original set are said to form S-pair if their sum is equal to 10. Show that every 5-element subset that does not contain an S-pair must contain 5. How...
  17. D

    Pigeon Hole Help needed

    Prove that the sequence 1967, 19671967, 196719671967,... contains an element that is divisible by 1969. thanx
  18. C

    Pigeon Hole problem!

    how do i show that in any set of 6 integers, there must be at least two whose difference is divisible by 5? thanks. Kyle
  19. J

    Pigeon Hole Principle Help!

    I know I am supposed to PHP to figure this out, but I just can't do it. Let n be a natural number. Show that if e1, e2, ..., e11 are different positive integers, then there are two of them, call them ei, ej, such that (n^ei) - (n^ej) is divisible by 10. Any ideas? Thanks.
  20. D

    pigeon hole principle

    if A and B are finite sets with |B|=n and |A| >= kn + 1 where k and n are positive integers and f:A--->B, then there exists a b within B such that |f^-1(b)| >= k+1. Does anyone know how to prove this?