6
votes
3answers
497 views

General Pigeonhole Principle - Coin Flips

I am trying to solve a problem using the general Pigeonhole Principle. The problem statement is as follows: A coin is flipped three times and the outcomes recorded. So, HTT might be recorded ...
2
votes
2answers
101 views

Pigeonhole principle and finite sequences

Suppose we have $75$ boxes that are labeled from $1$ to $75$ and that in each box there is at least one ball, but there are not more than $125$ balls total. I'm trying to find the largest number $n ...
0
votes
0answers
75 views

How do you justify the PigeonHole principle?

I am working on the problem below and just have two questions pertaining to my answers. 1) Am I clearly and correctly justfying my answers, anything I can improve on or explain better? 2) Are my ...
1
vote
1answer
63 views

In a class of 50 students, how many students are guaranteed to get the same score on an equally-weighted 20 question quiz?

I am completely lost... Any help is greatly appreciated. I am unsure where to go to better understand the concepts behind this problem. The problem: In a class of 50 students, how many students are ...
0
votes
1answer
58 views

pigeons and pigeonhole [closed]

Twenty cards numbered 1 to 20 are placed face down on a table. Cards are selected one at a time and turned over. If two of the cards add up to 21, the player loses. Use pigeonhole principle to show ...
6
votes
4answers
105 views

Pigeon Hole. 80 numbered balls

We have $80$ numbered balls(From $1$ to 80).Among which are $45$ blue and $35$ orange. Prove that at least two blue balls differ by $9$. For example $13$ and $22$ or $69$ and $78$. So they can differ ...
2
votes
2answers
99 views

Pigeon hole principle with sum of 5 integers

Prove that from 17 different integers you can always choose 5 so the sum will be divisible by 5. I tried with positive,negative numbers. Even, odd numbers etc but can't find the solution. Any ...
2
votes
3answers
193 views

Pigeonhole Principle -

Let $n$ be an odd integer and let $f$ be an $n$-permutation of length $n$. Show that the number \begin{equation}x = (1-f(1))\cdot(2-f(2))\cdot...(n-f(n))\end{equation} is even. I don't understand ...
0
votes
1answer
53 views

Combinatorial Question using ramsey's theory or pigeonhole principle??

We are currently going over pigeonhole principle, ramsey's theorem (graphs and such). Stuck on this particular question: Within a group of an odd number of people, show that at least one person knows ...
2
votes
1answer
76 views

Help with a pigeonhole principle?

Let $n \geq 1$ be an integer. Use the Pigeonhole Principle to prove that in any set of $n + 1$ integers from $\{1, 2, . . . , 2n\}$, there are two integers that are consecutive (i.e., di ffer by ...
0
votes
3answers
60 views

Pigeonhole Principle about division

Prove that, for any $n+1$ integers $a_{1},a_{2},....,a_{n+1}$, there exist two of the integers $a_{i}$ and $a_{j}$ with $i \neq j$, such that $a_{i} - a_{j}$ is divisible by $n$. Please help me about ...
1
vote
1answer
64 views

pigeonhole principle related problem

I'm given the problem: In a tournament which 18 teams participate, a team being matched with another in a round don’t match again in the follwoing (later) rounds. After 8 rounds prove that there are 3 ...
0
votes
2answers
118 views

Pigeonhole Principle and maximum length of the repeating section

The question I have is, when 5 / 20483 is written as a decimal, what is the maximum length of the repeating section of the representation? I believe I need to divide 5 by 20483 which is equal to ...
0
votes
2answers
97 views

Pigeon hole principle application [closed]

I am watching a lecture on pigeonhole principle at this link. At time 40:42, why does the instructor say that "either a will have 3 friends or 3 enemies". Why can't it be any of the other cases she ...
37
votes
6answers
4k views

Of any 52 integers, two can be found whose difference of squares is divisible by 100

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100. I was thinking about using recurrence, but it seems like pigeonhole may also ...
0
votes
1answer
59 views

What is the minimum number that must share the same birthday (month & day) each year, given that one such birthday is February 29?

If there are 6,392 students at Stack Exchange College. What is the minimum number that must share the same birthday (month & day) each year, given that one such birthday is February 29?
3
votes
2answers
267 views

Pigeonhole Principle: birthdays on same day of week

How many people must be in a room so that at least 10 have a birthday on a Friday? edit: Assume that no two people share the same birthday I'm somewhat confused and see two different ways to ...
0
votes
3answers
61 views

Picking three socks out of a drawer with two socks with two colors

How do I show that picking 3 socks containing just black and red socks that I must get either a pair of black or red socks? I mean it's fairly obvious, but how would I show it? Is this pigeon hole?
3
votes
3answers
117 views

Pigeonhole Principle Homework Problem

Seven boys and five girls are seated (in an equally spaced fashion) around a circular table with 12 chairs. Prove that there are two boys sitting opposite one another. I used 'G' for girls and 'B' ...
2
votes
1answer
79 views

Application of pigeonhole principle

Select $11$ diff erent numbers from $f\{1,2,...,20\}$. Prove that two of your numbers, $a$ and $b$, will diff er by two. Clearly this is an application of the pigeonhole principle. However, I'm not ...
4
votes
2answers
207 views

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 ...
0
votes
1answer
61 views

Induction and typical pigeonhole principle

Let $n,\,k,\,r,\,s\in\mathbb{N}$ and $0\leq r,s<n$. We have $nk+r$ objects placed in $n$ containers. Show that we can choose $s$ containers such that there is at least $sk+\min{\{r,\,s\}}$ objects ...
1
vote
0answers
132 views

Friend Group and Hater Group

Consider a set $S$ of $n$ people such that, for all distinct $x$ and $y$ in $S$, it is the case that either $x$ and $y$ like each other or $x$ and $y$ hate each other. Let us call $S' \subseteq S$ a ...
2
votes
1answer
108 views

pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle
2
votes
1answer
87 views

With the pigeon hole principle how do you tell which are the pigeons and which are the holes?

For example, I was reading this example from my textbook: Let S be a set of six positive integers who maximum is at most 14. Show that the sums of the elements in all the nonempty subsets of S ...
1
vote
2answers
104 views

Pigeonhole Question

This is an example from a Discrete math textbook: Any subset of size $6$ from the set $S = \{1,2, 4, \dots 9\}$ must contain two elements whose sum is $10$. Answer: Here the pigeons constitute a $6$ ...
0
votes
2answers
61 views

Pigeonhole question and generalization

Let H be a regular hexagon with side length 1 unit. (a) Show that if more than 6 points are speci ed inside H then the points of at least one pair of them are at most 1 unit apart. (b) State and ...
2
votes
2answers
89 views

Pigeonhole Principle Exercise

Show that any subset of $\{1, 2, 3, ..., 200\}$ having more than $100$ members must contain at least one pair of integers which add to $201$. I think it is doable using the Pigeonhole Principle.
4
votes
2answers
145 views

Minimum number of coins to ensure 10 coins of one type are selected

One coin is labelled with the number $1$, two different coins are labelled with the number $2$, three different coins are labelled with the number $3$, $\ldots$ , forty-nine different coins are ...
3
votes
2answers
114 views

Pigeonhole Principle - numbers between $1$ and $100$

Of the set $A=${$1,2,...,100$}, we will choose $51$ numbers. Prove that, among the $51$ chosen numbers, there are two such that one is multiple of the other My notes: 1) There are $25$ prime numbers ...
0
votes
1answer
56 views

Pigeonhole Principle to solve question straightforward

A store wants to celebrate its anniversary and will give a $200 shopping certi cate to the first customer to enter the store whose birthday is the same as that of two other previously admitted ...
0
votes
1answer
67 views

Solve using Pigeonhole principle

There are 45 candidates appear in an examination. prove that there are at-least two candidates in class whose roll numbers differ by a multiple of 44. How can I prove this using pigeonhole ...
3
votes
1answer
96 views

Generalizations of the pigeonhole principle

Let us place the numbers $1,2,3....,10$ in a random order on a circular table with 10 places. The question is: prove that there are three consecutive numbers with a sum of 17 or more. I know that we ...
2
votes
2answers
65 views

A combinatorics problem

Given $A = \{a_0, a_1,...,a_m\}$ such that it's a subset of $\{1,2,...,n\}$ where $m>n/2$, and $a_0$ is the smallest number in $A$. Show that $A$ contains two numbers $b$ and $c$ such that ...
3
votes
2answers
113 views

Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?
13
votes
3answers
508 views

Prove that if 33 rooks are placed on a chessboard, at least five don't attack one another

The question asks to prove that when 33 rooks are placed on an $8 \times 8$ chessboard that there are a total of 5 rooks that aren't attacking each other. What I know: 64 squares Rooks attack in ...
4
votes
1answer
1k views

Prove that at a party with at least two people, there are two people who know the same number of people…

Okay, now, I really want to solve this on my own, and I believe I have the basic idea, I'm just not sure how to put it as an answer on the homework. The problem in full: "Prove that at a party ...
2
votes
4answers
496 views

Pigeonhole principle: show that a class of nine has at least five male or five female students.

Here is the problem in full, start to finish, with no other special instructions or rules: "If there are 9 students in a class, show that at least 5 must be male or at least 5 must be female. Also, ...
3
votes
2answers
104 views

Pigeonhole principle and a decagon

This is a homework Question and has to do with Pigeonhole principle. Could use a hint. Q. The numbers ${0,1,2,.....9}$ are randomly assigned to the vertices ${x_0,x_1,...x_9}$ of a decagon. Show that ...
1
vote
2answers
120 views

pigeonhole principle homework question

These are Homework question. They are pigeon hole principle questions and I have a very hard time with these unless I have worked on a similar problem before. Q.1. Prove that if we select 87 numbers ...
1
vote
3answers
95 views

Pigeonhole principle application sums and differences

Let $A \subset \{1,2,...,99\}$, prove or disprove the following: a. For $|A| = 27$ b. For $|A| = 26$ There are $2$ different numbers in $A$ that their sum or their difference can be divided with ...
0
votes
1answer
67 views

There are 50 rooms in a line. If there are 26 rooms with girls, prove there are two girls exactly 5 rooms apart.

There are 50 rooms in a line. If there are 26 rooms with girls, prove there are two girls exactly 5 rooms apart. My idea was place 25 girls in into pairs of rooms, and there is no scenario which ...
0
votes
3answers
76 views

Pigeon holes principle

Let $P$ be a group that it's elements are 257 sentences in which only atomic sentences from $A,B,C$ exist (i.e. $A \iff B,\space\space A \wedge B \wedge C, \space\space...$) Show that there exists two ...
0
votes
1answer
59 views

Using The Pigeon-Hole Principle

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. ...
3
votes
1answer
43 views

Smallest subset of $\{1,2,…,4n\}$ with a certain property

Fact 1: Let $A\subseteq\{1,2,...,2n\}$. If $n+1\leq |A|$, then there exists 2 elements $a,b\in A$ such that $a+b=2n+1$. Proof: This can be shown by writing $\{1,2,...,2n\}$ as the union of $n$ ...
-2
votes
2answers
145 views

Pigeonhole Principle

Explain the following using Pigeonhole Principle is it is true: 1) If we choose 10 points in a $3 x 3$ inch square, there must be two points of the 10 which are at distance less than or equal to ...
4
votes
1answer
208 views

discrete math about Pigeonhole Principle

Prove that any set of $10$ positive integers less than or equal to $100$ will always contain two subsets with the same sum. Can anyone help me with this problem? Thanks.
9
votes
3answers
411 views

A question related to Pigeonhole Principle

In a room there are 10 people, none of whom are older than 60, but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of ...
42
votes
1answer
1k views

A discrete math riddle

Here's a riddle that I've been struggling with for a while: Let $A$ be a list of $n$ integers between 1 and $k$. Let $B$ be a list of $k$ integers between 1 and $n$. Prove that there's a non-empty ...
2
votes
2answers
115 views

Discrete Mathematics - Ice Cream random samples

How would you solve the following problem with Discrete Mathematics, and what is the answer? Suppose there are 5 different types of ice cream you like. How many random samples ice cream must be eaten ...