Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

1
vote
3answers
206 views

Pigeon Hole Principle Algorithm

The “pigeonhole principle” states that if n+1 objects (e.g., pigeons) are to be distributed into n holes then some hole must contain at least two objects. This observation is obvious but useful. ...
2
votes
2answers
102 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 ...
0
votes
2answers
36 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 ...
0
votes
2answers
92 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
133 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 ...
5
votes
1answer
136 views

Set theory: Metamath Proof of the Pigeon-Hole Principle, Error?

I have recently came discovered Metamath. Supposedly the language is one that a computer may proof-check. I then began to look at concepts that I am familiar with, and decided to look up the pigeon ...
3
votes
1answer
140 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 ...
3
votes
1answer
99 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 ...
2
votes
1answer
180 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
86 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
1answer
48 views

Midpoints joining integers on a plane lattice

How can you prove that if five nodes of a plane lattice are chosen at random then, the midpoint of the segment between the two points is a lattice point.
1
vote
1answer
118 views

pigeonhole principle exercises

I have an exam in combinatorics on friday and the Pigeonhole principle is a part of the material. Can someone give me a reference to a book with the hardest(!) questions in this material? than you ...
0
votes
1answer
45 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
1answer
46 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 ...
0
votes
1answer
82 views

Pigeonhole principle questions

I want to solve the following problems with Pigeonhole principle. Show that in every group of people that have atleast 2 people, we can find couple that know the number of the people in the group.( ...
0
votes
1answer
72 views

Coloring the Cartesian coordinate

Color every point of $\mathbb{R}^2$ either red (r) or blue (b). Show some rectangle has its vertices all the same color. I know that if you take say 3 points in a row on the x-axis that those three ...
0
votes
1answer
85 views

Consider a set A of 100, 000 arbitrary integers. Prove that there is some subset of 22 integers that end in the same last three digits.

Consider a set A of 100, 000 arbitrary integers. Prove that there is some subset of 22 integers that end in the same last three digits. I'm new to this principle and need help on this problem.
0
votes
1answer
86 views

Another version of PP

Prove the following version of the pigeonhole principle. Let $m$ and $n$ be positive integers. If $m$ objects are distributed in some way among $n$ containers, then at least one container must hold at ...
-5
votes
1answer
40 views

can any one help me with this pigeonhole question?

I try to solve it but i don't have enough time cuz it dues tomorrow. And I have no clue to solve it. hope you guy can help me out with this!
5
votes
0answers
185 views

How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

This a shortened version (motivation from telecommunications stripped away) of a question I asked in MO in late May (no answers). I am mostly checking, if somebody has seen this or a related question ...
1
vote
0answers
39 views

My first proof employing the pigeonhole principle / dirichlet's box principle - very simple theorem on real numbers. Please mark/grade.

What do you think about my first proof employing the pigeonhole principle? What mark/grade would you give me? Besides, I am curious about whether you like the style. Theorem Among three elements ...
1
vote
0answers
46 views

$x_1,x_2,\ldots,x_m$ is a permutation of $1,2,\ldots,m$ and $n_1,n_2,\ldots,n_m$ be integer and $m>1$ and odd.

$x_1,x_2,\ldots,x_m$ is a permutation of $1,2,\ldots,m$ and $n_1,n_2,\ldots,n_m$ be integer and $m>1$ and $m$ is odd. Now, $f(x)$ be defined as $f(x)=\sum\limits_{i,j=1}^{m} n_ix_j$. If $a,b$ are ...
1
vote
0answers
54 views

How to estimate pigeonhole principle?

I was thinking about this after my professor mentioned the pigeonhole principle in class. Let's say we have $N$ items and $M$ containers. Here we assume $N > M$. We will randomly place each of the ...
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 ...
1
vote
0answers
58 views

Pigeon Hole Principle : Can one of the games be played?

Q: 9 people are in a club. Each of them can play one of the games among Bridge , Hearts & Mahajong. Prove that they can play at least one of the mentioned games.( all games require 4 players.) I ...
0
votes
0answers
68 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 ...
0
votes
0answers
21 views

Pigeon hole principle question of dates and days and year.

In last decade in one febuary,5 children were born on same day of the week,but on different dates.explain how can this happen?what are the different date on they are born?If the new year day that year ...