4
votes
0answers
129 views

Select 100 integers from 1,2,…,200

Prove that if 100 integers are chosen from 1,2,...,200, and one of the integers chosen is less than 16, then there are two chosen numbers such that one of them is divisible by the other. Thanks in ...
1
vote
1answer
29 views

Proving minimum exsistence of intersection cardinality

Let $F_1,F_2...F_{13}$ be sets such that $\forall 1\le i \le 13: F_i\subseteq [10]$ and $|F_i|=6$ when $[10]={1,2,3...10}$ prove that there are $1 \le j < k < l \le 13$ such that $|F_j \cap F_k ...
2
votes
2answers
74 views

Chords of a 20-gon

Twenty points lie on a circle, so as to form a regular polygon. Then they are split into ten pairs, and the points in each pair are connected by a chord. Prove that some pair of these chords have the ...
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 ...
1
vote
1answer
61 views

Combinatorics pigeonhole principle question.

There are $n$ people at a meeting, each of whom chooses $3$ distinct numbers between $1$ and $11.$ $\quad({\sf a})$ What is the smallest value of $n$ which guarantees that at least two people choose ...
0
votes
1answer
28 views

Divisibility combinatorics

Let $A$ be a set of $1008$ positive integers bounded above by $2014$. It is then said that there must be two integers in $A$ such that one divides the other but I can't immediately see how to prove ...
1
vote
2answers
67 views

From any list of $131$ positive integers with prime factor at most $41$, $4$ can always be chosen such that their product is a perfect square

Author's note:I don't want the whole answer,but a guide as to how I should think about this problem. BdMO 2010 In a set of $131$ natural numbers, no number has a prime factor greater than 42. ...
2
votes
1answer
42 views

Seems straightforward pigeonhole

If we are given $37$ integers then show that it is possible to choose $7$ of them with sum divisible by $7$. I have tried this problem but with no avail. If we assume there are no integers with ...
1
vote
1answer
93 views

Pigeonhole Principle Question: Given any 5 points inside a square of side length 2, there is always a pair whose distance apart is at most $\sqrt2$

The question I am looking at: Prove that given 5 points inside a square of side length 2, it is always possible to find two of them whose distance apart is at most $\sqrt2$. This looks to me like I ...
2
votes
2answers
73 views

A question about the Pigeonhole Principle and linear equations over $\mathbb{Z}$

This may be a bit trivial (apologies if it is), but I was wondering if there was an elementary way to compute the cardinality of the solution set in the following situation: How many solutions would ...
1
vote
1answer
46 views

Show there exists a sequence of days within $49$ days where exactly $20$ hrs. are worked

Assume an integer number of hours will be worked each day for $49$ consecutive days. Further assume that at least $ 1 \frac{\text{hrs}}{\text{day}}$ and at most $11 \frac{\text{hrs}}{\text{wk}}$ can ...
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 ...
2
votes
2answers
46 views

Prove:that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014

Show that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014 without remainder ($i\not=j$). I think the "pigeonholes" here ...
2
votes
1answer
53 views

pigeonhole principle question 40 participants in an art workshop

There are 40 participants in an art workshop. Each one of them signed up for one or more of the following courses: handicraft, ceramics and Chinese paintings. One of the combinations of courses must ...
1
vote
1answer
83 views

Is there a Pigeon hole principle proof

Let $a_i$, $1 \leq i \leq 5$ denote five positive real numbers such that $\sum_{i =1}^{5}a_i = 100$. Show that there exist a pair $a_i,a_j$ such that $|a_i-a_j|\leq 10$. Is there a proof using pigeon ...
4
votes
1answer
255 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
2
votes
3answers
151 views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
4
votes
1answer
125 views

Math and chess question!

Given a $6\times6$ chess board with $13$ marked squares, can you always place three mutually non-attacking rooks on the marked squares? If so, how can this be proven?
2
votes
4answers
141 views

Pigeonhole principle for dominoes.

Suppose we have 13 dominoes, each with a red and blue integer number. Prove that there is a subset of 4 dominoes such that the sum of the 4 red numbers and the sum of the 4 blue numbers are both ...
1
vote
1answer
57 views

Pigeonholing mod 4 points on plane.

I have the following problem as homework. Suppose there are 13 points in the plane, all with integer coordinates. Prove at least one quadrilateral with vertices on those points has a barycentre with ...
2
votes
2answers
46 views

$2^n$ modulo n where n is odd always yields either an even or $1$

I'm attempting to do a pidgeonhole proof to prove that for some odd integer n, there is always a $2^k$ such that $2^k \mod(n) = 1$. I know that $2^n \mod(n)$ will always yield either an even number or ...
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 ...
1
vote
2answers
916 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 ...
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 ...
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
62 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 ...
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 ...
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 ...
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?
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 ...
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 ...
0
votes
3answers
121 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 ...
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 ...
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?
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 ...
4
votes
2answers
208 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 ...
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
2answers
81 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 ...
2
votes
1answer
97 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, ...