Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

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
73 views

Proving something using Pigeonhole Principle [duplicate]

How do I prove the following using the Pigeonhole principle? Let $n$ be an odd integer. Prove that there exists a positive integer $k$ such that $2^k \mod n = 1$. I don't understand how I can prove ...
4
votes
1answer
129 views

If one eats $100$ chocolates in $58$ days,then he must be eating exactly 15 chocolates in some consecutive days

BdMO 2014 Nationals $X$ eats 100 chocolates in 58 days,eating at least 1 chocolate per day.Prove that,in some consecutive days,she ate exactly 15 chocolates. I tried using the pigeonhole ...
20
votes
1answer
1k views

if there are 5 points on a sphere then 4 of them belong to a half-sphere.

If there are 5 points on the surface of a sphere then there is a closed half sphere containing at least 4 of them. It's in a pidgeonhole list of problems, but I think I have to use rotations in more ...
1
vote
2answers
918 views

If n is an odd integer, show there exists a positive integer k such that 2^k mod n = 1.

Hi I've been trying to solve this problem for at least 4 hours now but I can't figure it out. If anyone can help I would really appreciate it! I am asked to prove this using the pigeonhole principle: ...
1
vote
1answer
53 views

If $n\nmid a,a+d,a+2d. . . a+(n-1)d$,then $(n,d)=1$

None of the numbers in the sequence $a,a+d,a+2d,a+3d. . . a+(n-1)d$ are divisible by $n$.Then we have to prove that d and n are coprime. I am supposed to use the pigeonhole principle for this ...
0
votes
1answer
54 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 ...
0
votes
3answers
48 views

What Does “less than or equal to 1 apart” Mean?

I thought this question was classified as a word-meaning question. So, does "1 apart" mean 1/2 the side of the triangle? reference:
2
votes
1answer
222 views

Proving the Chinese Remainder Theorem using the Pigeonhole Principle

I am trying to prove a version of the Chinese Remainder Thoerem using the pigeonhole principle. The theorem that was provided: If n and m are relatively prime, then for all integers 0 ≤ a < n ...
2
votes
1answer
45 views

Prove, that in the subset of $\{1,\ldots,150\}$ there are two disjoint pairs with the same sums.

Prove, that in the subset with cardinality $25$ of $\{1,\ldots,150\}$ there are two disjoint pairs with the same sums. Well, there are at most $150+149=299$ possibilities of sums. But if we have a ...
1
vote
2answers
196 views

Prove a number is even using the Pigeonhole Principle

Let n be an odd integer and let f be an [n]-permutation of length n, where [n] is the set of integers 1, 2, 3,...n Show that the number ...
1
vote
1answer
63 views

Choosing $2n-1$ points from $n\times n$ grid such that $3$ points always form a right triangle

NOTE: Looking for a hint,not the whole solution. BdMO 2012 Nationals Secondary Consider a $n×n$ grid of points. Prove that no matter how we choose $2n-1$ points from these, there will always ...
1
vote
2answers
40 views

combinatorics - permutations question, possibly with pigeon hole

Let $A \in Mat_n(\mathbb R)$ such that $\forall i,j: a_{ij}\geq 0$ We are given: $$\forall j: \sum_{i=1}^n a_{ij}=\sum_{i=1}^n a_{ji}=1$$ show there's a permutation $\pi \in S_n$ such that $$\forall ...
2
votes
1answer
46 views

Prove that in each coloring of a $4\times7$ board in two colors there's a square that all four of it's corners are colored by the same color

Prove that in each coloring of a $4\times7$ board in two colors there's a square that all four of it's corners are colored by the same color. This is a pigeon hole principle question and I have a ...
0
votes
1answer
85 views

Pigeonhole Principle Discrete Math

At a dinner party there are 8 guests. The dinner takes place a table shaped like a regular octagon. Each edge has a place setting labeled with the name of a different guest. Originally each person ...
1
vote
1answer
50 views

Combinatorics - possibly pigeon hole, 100 by 100 matrix with numbers from 1 to 100

We are given a $100$ by $100$ matrix. Each number from $\{1,2,...,100\}$ appears in the matrix exactly a $100$ times. Show there is a column or a row with at least $10$ different numbers. I'd like a ...
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
2answers
44 views

Couple of Counting (how many ways) questions.

1.If I have a group of 10 seats reserved for people, and there are n=>10 total people, how many ways are there to choose who gets the 10 seats? for ex:If there was a definite number of people lets ...
5
votes
4answers
151 views

$x$ is equal to at least $51$ of $a_1,\frac{a_1+a_2}{2},\ldots,\frac{a_1+a_2+\ldots+a_{100}}{100}$. Prove that $2$ of $a_1,\ldots,a_{100}$ are equal.

If $x$ is equal to at least $51$ number of the array $a_1, \frac{a_1+a_2}{2},\ldots,\frac{a_1+a_2+\ldots+a_{100}}{100}$, prove that $2$ numbers of the array $a_1,a_2\ldots,a_{100}$ are equal. ...
1
vote
1answer
43 views

Composite Polynomials over UFDs

I was sitting in the Math room at my school and was reading the AMA Monthly and came across the proof for the following problem: Let $R$ be any UFD that is not a field. Suppose that $R$ has only ...
0
votes
3answers
61 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 ...
4
votes
1answer
57 views

let $A$ be a set of $n+1$ natural numbers between $1$ and $3n$. Show that there are $a,b \in A$ such that $n \leq a-b \leq 2n$

I'm having difficulties solving this question and would appreciate a nudge in the right direction. I think this is best solved with pigeonhole, but what are the pigeons and what are the holes?
0
votes
1answer
49 views

Pigeon Hole Principle (involving distances)

There are 100 old(non-digital) watches in an antique shop, all running but not necessarily on time. Prove that at some moment of time the sum of the distances from the center of the shop to the ...
3
votes
1answer
104 views

Pigeonhole principle problem involving circle and its chords

Several chords are drawn in a circle of radius 1 such that each diameter intersects no more than 4 of them. Prove that the sum of their lengths does not exceed 13.
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 ...
1
vote
1answer
47 views

Arangement of six circles in a plane

Six circles (including their circumferences and interiors) are arranged in the plane so that no one of them contains the center of another. Prove that they [the six circles] cannot have a point in ...
0
votes
1answer
104 views

650 points inside a circle of radius 16

There are 650 points inside a circle of radius 16. Prove there exists a ring with inner radius 2 and outer radius 3 covering 10 of these points. Hint of the professor: Use Dirichlet's (pigeonhole) ...
7
votes
1answer
205 views

Proof that Fibonacci Sequence modulo m is periodic?

It's well known that the Fibonacci sequence modulo m (where m is any integer) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more complicated. ...
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 ...
3
votes
1answer
61 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
76 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
88 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
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 ...
4
votes
1answer
81 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
122 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
64 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
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?
2
votes
1answer
119 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
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
1answer
60 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
72 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
47 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
73 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
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 ...
1
vote
3answers
150 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
56 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
52 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 ...