kokomocutie88r1

Answered

2022-07-16

Prove that among any 100 integers there are always two whose difference is divisible by 99. How can I prove this?

Answer & Explanation

phravincegrln2

Expert

2022-07-17Added 19 answers

Step 1

Let ${r}_{i}$ be the remainder when the i-th integer in our list is divided by 99.

There are only 99 conceivable remainders, the numbers 0 to 98.

Step 2

Since there are 100 integers in our list, and only 99 conceivable remainders, there must be two different numbers in our list which have the same remainder. This is a consequence of the Pigeonhole Principle, but the fact is clear even without a name for it.

Finally, if two numbers have the same remainder on division by 99, their difference is divisible by 99.

Let ${r}_{i}$ be the remainder when the i-th integer in our list is divided by 99.

There are only 99 conceivable remainders, the numbers 0 to 98.

Step 2

Since there are 100 integers in our list, and only 99 conceivable remainders, there must be two different numbers in our list which have the same remainder. This is a consequence of the Pigeonhole Principle, but the fact is clear even without a name for it.

Finally, if two numbers have the same remainder on division by 99, their difference is divisible by 99.

phepafalowl

Expert

2022-07-18Added 4 answers

Step 1

Here's a proof requiring no knowledge of division or remainders. Suppose a counterexample exists, i.e. there are 100 integers $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{1},\dots ,{\mathrm{a}}_{100}\phantom{\rule{mediummathspace}{0ex}}$ such that $\phantom{\rule{mediummathspace}{0ex}}\mathrm{i}\ne \mathrm{j}\phantom{\rule{mediummathspace}{0ex}}\Rightarrow \phantom{\rule{mediummathspace}{0ex}}99\nmid {\mathrm{a}}_{\mathrm{i}}-{\mathrm{a}}_{\mathrm{j}}.\phantom{\rule{mediummathspace}{0ex}}$. Then they are distinct, so we may index them so that they're strictly ordered $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{1}<{\mathrm{a}}_{2}<\dots <{\mathrm{a}}_{100}.\phantom{\rule{mediummathspace}{0ex}}$. Now if $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{100}\ge {\mathrm{a}}_{1}\phantom{\rule{negativethinmathspace}{0ex}}+99\phantom{\rule{mediummathspace}{0ex}}$ then by replacing $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{100}\phantom{\rule{mediummathspace}{0ex}}$ by $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{100}-99\phantom{\rule{mediummathspace}{0ex}}$ and reordering we obtain a new counterexample of smaller interval length ($=max-min+1$), since the new sequence has the same min, by $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{100}\phantom{\rule{negativethinmathspace}{0ex}}-99\ge {\mathrm{a}}_{1},\phantom{\rule{mediummathspace}{0ex}}$, but has smaller max ${\mathrm{a}}_{99}<{\mathrm{a}}_{100},\phantom{\rule{mediummathspace}{0ex}}$, and the new sequence remains a counterexample, since $\phantom{\rule{mediummathspace}{0ex}}\phantom{\rule{mediummathspace}{0ex}}99\mid {\mathrm{a}}^{\prime}\phantom{\rule{negativethinmathspace}{0ex}}-\phantom{\rule{negativethinmathspace}{0ex}}\mathrm{a}\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}99\mid {\mathrm{a}}^{\prime}\phantom{\rule{negativethinmathspace}{0ex}}-(\mathrm{a}\phantom{\rule{negativethinmathspace}{0ex}}-\phantom{\rule{negativethinmathspace}{0ex}}99).\phantom{\rule{mediummathspace}{0ex}}$.

Step 2

Thus the least length counterexample must have length $\le 99,\phantom{\rule{mediummathspace}{0ex}}$, hence its 100 integers all lie in the length 99 interval of consecutive integers $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{1},{\mathrm{a}}_{1}\phantom{\rule{negativethinmathspace}{0ex}}+\phantom{\rule{negativethinmathspace}{0ex}}1,\dots ,{\mathrm{a}}_{1}\phantom{\rule{negativethinmathspace}{0ex}}+\phantom{\rule{negativethinmathspace}{0ex}}98.\phantom{\rule{mediummathspace}{0ex}}$. Therefore, by the pigeonhole (box) principle, two of the integers are equal, a contradiction.

Here's a proof requiring no knowledge of division or remainders. Suppose a counterexample exists, i.e. there are 100 integers $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{1},\dots ,{\mathrm{a}}_{100}\phantom{\rule{mediummathspace}{0ex}}$ such that $\phantom{\rule{mediummathspace}{0ex}}\mathrm{i}\ne \mathrm{j}\phantom{\rule{mediummathspace}{0ex}}\Rightarrow \phantom{\rule{mediummathspace}{0ex}}99\nmid {\mathrm{a}}_{\mathrm{i}}-{\mathrm{a}}_{\mathrm{j}}.\phantom{\rule{mediummathspace}{0ex}}$. Then they are distinct, so we may index them so that they're strictly ordered $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{1}<{\mathrm{a}}_{2}<\dots <{\mathrm{a}}_{100}.\phantom{\rule{mediummathspace}{0ex}}$. Now if $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{100}\ge {\mathrm{a}}_{1}\phantom{\rule{negativethinmathspace}{0ex}}+99\phantom{\rule{mediummathspace}{0ex}}$ then by replacing $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{100}\phantom{\rule{mediummathspace}{0ex}}$ by $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{100}-99\phantom{\rule{mediummathspace}{0ex}}$ and reordering we obtain a new counterexample of smaller interval length ($=max-min+1$), since the new sequence has the same min, by $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{100}\phantom{\rule{negativethinmathspace}{0ex}}-99\ge {\mathrm{a}}_{1},\phantom{\rule{mediummathspace}{0ex}}$, but has smaller max ${\mathrm{a}}_{99}<{\mathrm{a}}_{100},\phantom{\rule{mediummathspace}{0ex}}$, and the new sequence remains a counterexample, since $\phantom{\rule{mediummathspace}{0ex}}\phantom{\rule{mediummathspace}{0ex}}99\mid {\mathrm{a}}^{\prime}\phantom{\rule{negativethinmathspace}{0ex}}-\phantom{\rule{negativethinmathspace}{0ex}}\mathrm{a}\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}99\mid {\mathrm{a}}^{\prime}\phantom{\rule{negativethinmathspace}{0ex}}-(\mathrm{a}\phantom{\rule{negativethinmathspace}{0ex}}-\phantom{\rule{negativethinmathspace}{0ex}}99).\phantom{\rule{mediummathspace}{0ex}}$.

Step 2

Thus the least length counterexample must have length $\le 99,\phantom{\rule{mediummathspace}{0ex}}$, hence its 100 integers all lie in the length 99 interval of consecutive integers $\phantom{\rule{mediummathspace}{0ex}}{\mathrm{a}}_{1},{\mathrm{a}}_{1}\phantom{\rule{negativethinmathspace}{0ex}}+\phantom{\rule{negativethinmathspace}{0ex}}1,\dots ,{\mathrm{a}}_{1}\phantom{\rule{negativethinmathspace}{0ex}}+\phantom{\rule{negativethinmathspace}{0ex}}98.\phantom{\rule{mediummathspace}{0ex}}$. Therefore, by the pigeonhole (box) principle, two of the integers are equal, a contradiction.

Most Popular Questions