Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

4
votes
2answers
203 views

Guaranteeing an integer lattice point centroid

My question is this: Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$. I ...
4
votes
3answers
148 views

proof using pigeonhole principle

I am struggling to come up with a proof to the following question(from cut-the-knot.org): Prove that if n is odd,then for any permutation $p$ of the set $\{1,2,3...,n\}$ the product $$P(p) = ...
4
votes
1answer
220 views

$16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

There are $16$ natural numbers placed next to each other. Each is a number from $0$ to $9$. These are in any order, and you can have as many repeats as you want (e.g. all $16$ numbers can be zero, or ...
4
votes
1answer
94 views

10 points inside a square - minimum distance between any of them

A square of side 1 is given, and 10 points are inside the square. If we divide the square into 9 smaller squares, and apply Dirichlet principle, we can prove that there are 2 of these 10 points whose ...
4
votes
1answer
260 views

If any x points are elected out of a unit square, then some two of them are no farther than how many units apart?

If 5 points are randomly positioned in a unit square, no two points can be greater than square root of 2 divided by 2 apart; divide up the unit square into four squares, and, based on the pigeonhole ...
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 ...
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 ...
4
votes
1answer
1k views

Combinatorics - pigeonhole principle question

This is for self-study. This question is from Rosen's "Discrete Mathematics And Its Applications", 6th edition. An arm wrestler is the champion for a period of 75 hours. (Here, by an hour, we mean a ...
4
votes
1answer
130 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 ...
4
votes
0answers
139 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 ...
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 ...
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?
3
votes
1answer
128 views

geometric problem solved with Pigeon Hole Principle

The problem is: Show that among any 5 points in a equilateral triangle of unit side length, there are 2 whose distance is at most 1/2 units apart.
3
votes
3answers
118 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' ...
3
votes
2answers
1k views

Subsets with equal sums

I have a problem to solve but I am in need of your help. Subjects with equal sums: Prove that for every set $A$ which consists of $10$ double digit natural numbers( numbers among $10, \ldots, 99$), ...
3
votes
2answers
118 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 ...
3
votes
1answer
72 views

Prove by using Pigeon Hole Principle

Let $k \in \mathbb Z^+ $. Prove that there exists a positive integer $n $ such that $k|n$ and the only digits in $n$ are 0's and 3's
3
votes
5answers
363 views

The Pigeon Hole Principle and the Finite Subgroup Test

I am currently reading this document and am stuck on Theorem 3.3 on page 11: Let $H$ be a nonempty finite subset of a group $G$. Then $H$ is a subgroup of $G$ if $H$ is closed under the ...
3
votes
2answers
87 views

Pigeonhole Principle and Geometry

Consider any five points in the plane that have integer coordinates: -Prove that there are two points such that the midpoint of the line segment joining those two points also has integer coordinates
3
votes
2answers
268 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 ...
3
votes
2answers
110 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 ...
3
votes
1answer
123 views

Lower bound for the number of coin weightings

The book that I am currently studying has the following exercise. Given is a set of $n$ coins of weights $0$ or $1$ and a scale to weight them. We would like to determine the weight of each coin by ...
3
votes
1answer
97 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 ...
3
votes
3answers
151 views

Proof using pigeonhole and greatest integer (floor) function.

The question is to prove that if m is a positive integer then, $$[mx] = [x] + \left[x+\frac{1}{m}\right] +\left[x+\frac{2}{m}\right] + \cdots + \left[x+\frac{(m-1)}{m}\right] $$ for $x \in ...
3
votes
1answer
76 views

Pigeonhole Proof

Let $n_1,n_2,\ldots,n_t$ be positive integers. Show that if $n_1+n_2+\cdots+n_t-t+1$ objects are placed into $t$ boxes, then for some $i$, $i = 1,2,\ldots,t$, the $i$th box contatins at least $n_i$ ...
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 ...
3
votes
1answer
75 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 ...
3
votes
2answers
116 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$?
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$ ...
3
votes
1answer
320 views

Divisibility and Pigeonhole principle

Given a sequence of $p$ integers $a_1, a_2, \ldots, a_p$, show that there exist consecutive terms in the sequence whose sum is divisible by $p$. That is, show that there are $i$ and $j$, with $1 \leq ...
3
votes
1answer
108 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.
3
votes
1answer
207 views

Ramsey Type problem (variant of people at a party)

There is $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\lfloor n/2\rfloor-1$ of them, each of whom either knows both or else ...
3
votes
1answer
102 views

Pigeonhole proof of Rational Approximation Theorem

I am stuck with the solution to the following problem (it is also known as the Rational Approximation Theorem) at the Art of Problem Solving wiki, which states: Show that for any irrational $x \in ...
3
votes
1answer
102 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 ...
3
votes
0answers
103 views

Milk bottles and pigeonhole. [duplicate]

Possible Duplicate: Chess Master Problem A child drinks at least 1 bottle of milk a day. Given that he has drunk 700 bottles of milk in a year of 365 days, prove that for he has drunk ...
2
votes
4answers
617 views

A problem in discrete math (Pigeonhole principle related)

This question is from the multiple choice test: A circular region is divided by 5 radii into sectors, as shown above. Twenty-one points are chosen in the circular region, none of which is on any of ...
2
votes
3answers
124 views

A pigeonhole problem from “Conjecture and Proof”

I don't really know how to start this problem at all. I would like a solution or even hints. "Prove that for every odd integer $n$ there is an integer $i$ such that $n \mid 2^i- 1.$" The chapter in ...
2
votes
3answers
148 views

One of $2^1-1,2^2-1,…,2^n-1$ is divisible by $n$ for odd $n$

Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$. I know that pigeonhole principle would be helpful, but how should I apply it? ...
2
votes
2answers
221 views

The decimal expansion of the quotient of two integers

It is an exercise in a book on discrete mathematics.How to prove that in the decimal expansion of the quotient of two integers, eventually some block of digits repeats. For example: $\frac { 1 }{ 6 } ...
2
votes
3answers
256 views

Choose 38 different natural numbers less than 1000, Prove among these there exists at least two whose difference is at most 26.

Choose any 38 different natural numbers less than 1000. Prove that among the selected numbers there exists at least two whose difference is at most 26. I think I need to use pigeon hole principle, ...
2
votes
2answers
208 views

Question about the Pigeonhole Principle

The question is: Let $A = \{1,2,3,4,5,6,7,8\}$. If five integers are selected from $A$, must at least one pair of the integers have a sum of $9$? The book explains the solution by dividing the ...
2
votes
2answers
305 views

Pigeonhole principle question confusion

Now I understand it. I just learnt this principle. I am doing a problem in which there's a box with many red socks, green socks and blue socks. First question was how many minimum socks should I pick ...
2
votes
3answers
196 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 ...
2
votes
2answers
91 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.
2
votes
4answers
530 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, ...
2
votes
2answers
103 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
2answers
79 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
123 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 ...
2
votes
1answer
98 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, ...
2
votes
1answer
111 views

pigeonhole principle - 100 points in $13\times18$ rectangle

Prove that you can't arrange 100 points inside a $13\times18$ rectangle so that the distance between any two points is at least 2. I tried many ways to divide the rectangle, but I can't get the parts ...