Practice (Category=PigeonholePrinciple(133))

back to index  |  new

Show that, among randomly selected $11$ numbers from $1$, $2$, $3$, $\cdots$, $19$, $20$, one of them must be a multiple of another.

Show that among any 5 integers, three of them must satisfy the condition that their sum is a multiple of 3.

Show that in a $n$-people party, at least two of them have met the same number of other guests before.

There are only two problems in a math test. Ten points will be awarded for every correct answer. Two point will be given for any skipped problem. No point will be given for wrong answer. The teacher claims regardlessly there must be at least 3 students will end up with the same score. Can you figure out the minimal number of students who will take this test?

Is it possible to construct 12 geometric sequences to contain all the prime between 1 and 100?

Each point of a circle is colored either red or blue. (a) Prove that there always exists an isosceles triangle inscribed in this circle such that all its vertices are colored the same. (b) Does there always exist an equilateral triangle inscribed in this circle such that all its vertices are colored the same?

Given any five real numbers, show that at least two of them $x$ and $y$ satisfy the condition $|xy+1|>|x-y|$.

(Thue's theorem) Let $p$ be a prime. Show that for any integer $a$ such that $p\not\mid a$, there exist positive integers $x$, $y$ not exceeding $\lfloor{\sqrt{p}}\rfloor$ satisfying $ax\equiv y\pmod{p}$ or $ax\equiv -y\pmod{p}$.


Let $n$ be a positive odd integer. Show that at least one of the following numbers is a multiple of $n$. $$2-1, 2^2 -1, \cdots, 2^{n-1} -1$$


Show that from any given $m$ integers, it is always possible to select one or more integers such that their sum is a multiple of $m$.


Let $a$, $b$, and $x_0$ all be positive integers. Sequence $\{x_n\}$ is defined as $x_{n+1}=ax_n + b$ where $n \ge 1$. Show that $x_1$, $x_2$, $\cdots$ cannot be all prime.