Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

0
votes
2answers
131 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 ...
3
votes
1answer
65 views

Small Combinatorical Question - Pigeonhole Principle Related

Suppose there are $77$ positive integers arranged in a row such that their sum is $140$. I want to show there is a sequence of adjacent integers in the row whose sum is $13$. My line of thought is ...
2
votes
2answers
86 views

Polygon and Pigeon Hole Principle Question

Seven vertices are chosen in each of two congruent regular 16-gons. Prove that these polygons can be placed one atop another in such a way that at least four chosen vertices of one polygon coincide ...
2
votes
1answer
90 views

pigeonhole principle with sequence of numbers

Let $(x_1,x_2,x_3,\dots,x_{77})$ be positive numbers. Use the pigeonhole principle to show that, if $\sum_{i=1}^{77}{x_{i}} = 140$, then there exist $j$ and $k$ such that $\sum_{i=j}^{k}{x_{i}} = 13$. ...
0
votes
2answers
103 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 ...
4
votes
1answer
83 views

Elegant proof of icosohedron property

This problem was question A1 on the 2013 Putnam contest. Is there a better way to solve this problem than just using pigeonhole principle? Specifically, is there a group theoretic way to interpret ...
0
votes
3answers
138 views

How many people do you need to guarantee that two of them have the same initals?

An auditorium has a seating capacity of 800. How many seats must be occupied to guarantee that at least two people seated in the auditorium have the same first and last initials? I thought $26 \cdot ...
4
votes
2answers
70 views

Pigeonhole principle on two coloured circle

Suppose a circle is divided into 200 congruent sectors, with 100 of them coloured red and the other 100 blue. A smaller concentric circle is placed on the larger circle and also so divided and ...
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
62 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?
2
votes
1answer
141 views

Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10

Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10. I'm trying to apply the pigeonhole principle, but haven't been able to ...
3
votes
2answers
276 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
1answer
63 views

Pigeonhole Principle & Fermat's Little Theorm

I'm having a terrible time grasping Fermat's Little Theorem & then an even rougher time trying to use one to prove the other. Any help on this question would be tremendously appreciated! xx "The ...
1
vote
1answer
75 views

pigeonhole question with sets and sum of numbers

This question is meant to be solved with pigeonhole principle. But I can't solve it. I just can't figure out what is the pigeon and what is the pigeon hole. I don't really have a clear direction. ...
1
vote
1answer
50 views

Pigeonhole question - divisibility by chosen number

This question should be solved with pigeonhole principle. Let $a,n \in \mathbb N$ such that $a$ is a number whose digits are only $3$'s and $0$'s, and $n$ is an unspecified natural number. Show that ...
1
vote
1answer
76 views

Pigeonhole Principle question - sum of positive integers

A question that should be solved with pigeonhole but I'm having problems. $a_1,a_2,a_3,...,a_{77}$ are positive integers. We are given that $a_1+a_2+a_3+...+a_{76}+a_{77} < 133$ Show that there ...
0
votes
3answers
72 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
122 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
85 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 ...
1
vote
3answers
171 views

Generalized Pigeonhole Principle

Can somebody explain this to me? I am very confused. I have a question that says "What is the minimum number of students required in a discrete mathematics class to be sure that at least six will ...
1
vote
1answer
58 views

Pigeonhole problem - salvaging my solution

A student is solving combinatorics problems. Each day he solves at least one problem. He solves no more than 500 problems a year. Prove that there is an interval of days in which he solves 229 ...
1
vote
2answers
61 views

Max area of triangle -PHP

How do i prove that the maximum area that can be obtained among 3 random points in a square is half the area of the square?- I need it to for the following question " Show that among any 9 points ...
4
votes
2answers
219 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
64 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
1answer
69 views

using the pigeon hole principle to prove that some integer with a sequence of ones and zeros is divisible by some d

Let $d$ be any fixed natural number. Show that there must exist an integer of the form $11\ldots1100\ldots 00$ (that is a integer whose digits consist of a sequence of $1$'s followed by $0$'s) which ...
1
vote
3answers
237 views

Pigeonhole Principle Question - Group of 6 people, do 3 either know each other or not?

Prove that in any group of 6 people there are always at least 3 people who either all know one-another or all are strangers to one-another. Hint: Use the pigeonhole principle. I don't see how this ...
2
votes
1answer
97 views

Prove that there is an element in the given set having fractional part less than 0.01

Given a set $ \{ \sqrt{3}, 2\sqrt{3}, 3\sqrt{3},...\}$, prove that some of the elements have fractional part less than 0.01 when written in decimal form. Here is my attempt so far: Divide the range ...
1
vote
0answers
133 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
115 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
1
vote
1answer
68 views

How do you tell which are the pigeons and which are the pigeon holes? [closed]

I am unable to correctly identify pigeons and pigeon holes in word problems. What is the technique?
1
vote
2answers
82 views

90 people with ten friends in the group. Prove its possible to have each person invite 3 people such that each knows at least two others

A high school has 90 alumni, each of whom has ten friends among the other alumni. Prove that each alumni can invite three people for lunch so that each of the four people at the lunch table will know ...
0
votes
1answer
82 views

Perfect Fourth Power - Pigeon Hole Principle

Let $a_1, a_2, ..., a_n$ be positive integers all of whose prime divisors are $\le$ 13. Show that if $n \ge 193$ then there exists four of these integers whose product is a perfect fourth power. I ...
1
vote
3answers
119 views

Proof Involving Pigeonhole Principle

Let $a_1, a_2, ..., a_n$ be positive integers all of whose prime divisors are $\le$ 13. a) Show that if $n \ge 65$ then there exist two of these integers whose product is a perfect square. [DONE] b) ...
1
vote
2answers
112 views

Pigeonhole Principle Proof

2004 flies are inside a cube of side 1. Show that some 3 of them are within a sphere of radius 1/11. I am not sure how to begin the proof especially since we are asked to work on a sphere rather than ...
2
votes
2answers
149 views

Extended Pigeonhole Principle: How to prove it?

A version of the pigeonhole principle is: (1) If m objects are put in n boxes and n < m, then at least one box contains at least ceil(m/n) objects An alternate (more generalized) version ...
3
votes
1answer
77 views

Prove that for positive number, some multiple only has 0 and d as it's digits

Let $ n$ be a positive integer, and let $1<=d<=9$. Show that some multiple of $n$ has $0$ and $d$ as its only digits. I don't know how to even start this question. It's under the pigeonhole ...
2
votes
1answer
91 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 ...
5
votes
5answers
122 views

Pigeonhole principle problem involving inequality 0 < |$\sqrt{x} - \sqrt{y}$| < 1

21 integers are selected from {1, 2, 3, ..., 400}. Prove that two of them, say x and y, satisfy 0 < |$\sqrt{x} - \sqrt{y}$| < 1. I am confident you have to use and apply the Pigeon Hole ...
2
votes
1answer
101 views

Pigeonhole Principle / Number Theory

Let $S$ be a subset of $A=\{1,2,3,...,1000\}$. Find the largest number of elements in $S$ such that for any $a, b \in S$ with $a>b$, $a-b$ does not divide $a+b$. I've tried numerous approaches, ...
1
vote
2answers
110 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
93 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.
1
vote
1answer
65 views

English question regarding pigeonhole principle classic question.

Mr. and Mrs. Smith invited four couples to their home. Some guests were friends of Mr. Smith, and some others were friends of Mrs. Smith. When the guests arrived, people who knew each other ...
3
votes
1answer
104 views

pigeonhole principle on a circle

In a disk of radius 10, how can we find all values n such that there are exactly n points in the disk and such that no matter how the n points are arranged, we can draw a disk with radius 1 in the ...
4
votes
2answers
150 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 ...
2
votes
1answer
193 views

Probability problem- Are there atleast 3 balls with same colour radius and in same box?

The question is as follows, it came in RMO in 1990. It most likely involves probability..as far I think. Two boxes contain between them 65 balls of several different sizes. Each ball is white, black, ...
3
votes
2answers
120 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
58 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
63 views

Need help to prove pigeonhole problem

If we pick n+1 different positive integers with every integer is less than 2n. Prove that we can always find three numbers among these n+1 numbers that one is equal to the sum of the other two ...
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 ...