1
vote
1answer
40 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 ...
1
vote
0answers
48 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
1answer
56 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 ...
1
vote
1answer
44 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 ...
7
votes
1answer
164 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. ...
37
votes
6answers
3k 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 ...
2
votes
1answer
104 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
104 views

pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle
3
votes
2answers
106 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$?
4
votes
1answer
115 views

In a sequence of $n$ integers, must there be a contiguous subsequence that sums to a multiple of $n$?

Let $x_1, \ldots, x_n$ be integers. Then are there indices $1\le a\le b\le n$ such that $$\sum_{i=a}^b x_i$$ is a multiple of $n$?
0
votes
2answers
53 views

Given n numbers, prove that difference of at least one pair of these numbers is divisible by n-1

Suppose you have a list of $n$ numbers, $n\geq 2$. Let $A$ be the set of differences of pairs of the $n$ numbers. Prove or disprove that at least one element of A must be divisible by $n-1$. Anyone ...
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? ...
12
votes
6answers
395 views

Is Pigeonhole Principle the negation of Dedekind-infinite?

From Wiki, "The Pigeonhole Principle": In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more ...
2
votes
1answer
106 views

A game involving points in the integer plane - who wins?

I am running a workshop on puzzles and problem solving over the weekend and thought that it might be a good idea to get people engaged by phrasing some interesting mathematical results in terms of ...
7
votes
3answers
244 views

Prove that the product of primes in some subset of $n+1$ integers is a perfect square.

I am trying to prove the following: The set $A$ consists of $n + 1$ positive integers, none of which have a prime divisor that is larger than the $n$th smallest prime number. Prove that there ...
4
votes
1answer
213 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 ...