# Tagged Questions

Questions involving the pigeonhole principle, which states that if $n$ items are placed in $m$ containers and $n>m$, then one at least one container has more than one item.

2answers
74 views

### Pigeonhole Principle question - sum of natural numbers

Let $f:\{1,2,...,15\} \rightarrow \Bbb N$ be a function such that $\sum_{i=1}^{15} f(i) =100$. $f(15+1)$ is defined to be $f(1)$. I have shown that $14\leq f(i)+f(i+1)$ for some $1\leq i \leq15$ ...
2answers
117 views

### Help prove $f:X \rightarrow Y$ is an injection $\Leftrightarrow$ $f:X\rightarrow Y$ is a surjection when $|X|=|Y|$

I need to prove: Given non-empty finite sets $X$ and $Y$ with $|X| = |Y|,$ a function $X\rightarrow Y$ is an injection if and only if it is a surjection. The hint given is to use the pigeonhole ...
2answers
28 views

### Pigeon hole subset problem

For a given N numbers labeled from 1-N, we need to pick M numbers such that there are atleast K pairs of numbers(x,y) which statisfy x+y=N+1? can anyone help me out with this... please?
2answers
62 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 ...
1answer
124 views

0answers
43 views

### Proving the Pigeonhole Principle

I am looking to prove the Pigeonhole Principle by proving the following claim: Let $A$ be a set with $m$ elements, and let $B$ be a set with $n$ elements, where $m,n\in \omega$ and $m > n$. ...
0answers
47 views

### Solution of $Connect4^{TM}$

It says here that Connect4 can be won by Player $1$ if their first counter goes in the middle column $4$, a draw if they play in columns $3$ or $5$, and Player $1$ loses everywhere else. As far as I ...
0answers
92 views

### Prove that $ax^2 + by^2 \equiv c \ ( \mod{p})$ has integer solutions

Let $p$ be a prime number and $a, b, c$ integers such that $a$ and $b$ are not divisible by $p$. Prove that $ax^2 + by^2 \equiv c \ ( \mod{p})$ has integer solutions Well, this problem can be solved ...
0answers
21 views

### Pigeon hole principle:Trominoes and chessboards

Heres the question: What is the largest number of squares on an 8 $\times$8 checkerboard which can be colored green,so that in any one arrangement of three squares ("tromino"),at least one square ...
0answers
55 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 ...
0answers
136 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 ...
0answers
152 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 ...
0answers
89 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 ...
0answers
52 views

### Generalized pigeonhole principle Question

Question: The island of Tikong has seventeen villages and the rugby board needs to select a squad to be sent to the regional Oceania tournament to be held in Savulevu. What is the smallest size of the ...
0answers
52 views

### Applying pigeonhole principle to determine whether a list of strings must have duplicates.

Say you have a program that creates strings of lower-case letters of length 5 or less. It is told that the program holds 600,000 words on its drive. How can you figure out if all the words are ...
0answers
49 views

### How to prove members of this series differ from an integer by, at most, 1/n?

Consider the series , where a is a positive real number. $a, 2a, 3a, .... (n-1)a$ Prove that there is one member of this series that differs from an integer by at most $\frac{1}{n}$ My approach : ...
0answers
109 views

### Out of $513$ nine-digit numbers, there must be two with matching zero positions

Need help figuring this one out, came up in class and I have no idea how to write a proof for this. Prove: Given a collection of 513 Social Security numbers, there must be two that match zeros.
0answers
39 views

### Proof of Pigeonhole Principle using equipotence and induction

I am attempting to prove the form of the Pigeonhole Principle which states "$\forall n,m \in \mathbb{N}$, the set $\{1,\cdots,n+m\}$ is not equipotent to the set $\{1,\cdots n\}$". Here is my proof ...
0answers
58 views

### Pigeon Hole Principle - proof of d as a positive integer

Let $d$ be a positive integer and consider any set $A$ of $d+1$ positive integers. Show that there exists two different numbers $x, y\ \epsilon\ A$ so that $x \mod\ d = y \mod\ d$ and $x =/= y$. ...
0answers
79 views

### combinatorics - pigeonhole principle - 2

I've advanced a little with this question but I'm not sure that I'm in the right direction. For any set $X$ with $n$ positive numbers, $n>5$, prove the existiance of subset $Y \subset X$ so that ...
0answers
72 views

### Mantissa of $\pi$ and pigeonhole

It might be worth noting that this is a "pigeonhole principle" problem, but I'm not sure how to use PHP with it. The mantissa of $\pi$ is the fractional part of it (i.e. everything after the decimal ...
0answers
48 views

### four point in a row

We have painted all dots of page with two colors(blue and green), proof that there are four point with green color in a line that distance of any two neighbors of this four is one unit or there are ...