Is my argument correct to solve this textbook problem?

Question

The problem is from M.Bona's "A Walk through Combinatorics", Ch1 Prob 13:

There are infinitely many pieces of paper in a basket, and there is a positive integer written on each of them. We know that no matter how we choose infinitely many pieces, there will always be two of them so that the difference of the numbers written on them is at most ten million. Prove that there is an integer that has been written on infinitely many pieces of paper.

My attempt: Let $A$ a multiset of all positive integers written on the infinite pieces of paper. My claim is that (i) $A$ has a finite number of distinct numbers and (ii) there is at least one number from $A$ that is repeated for a an infinite number of times.
If (i) is true then (ii) should be true for if not then $A$ must have an infinite number of distinct positive integers.
(i) is true otherwise we can make a selection $B$ as follows: Let $a$ the minimum element of $A$, keep adding $b\gt10^7$. If the result is a member of $A$ then add it to $B$. This "algorithm" should not terminate if $A$ has infinite distinct numbers and then $B$ should be a selection of infinite many pieces from $A$ but no 2 numbers have a difference at most 10 million, i.e. a contradiction. In addition it is possible to construct a non empty $A$ for example taking $\{1,2,3\}$ an infinite number of times.
If (i) is true then so is (ii) and this proves the problem's statement

I am not familiar with the concept of infinity and so I found this problem challenging. The book provides a different answer which I haven't digested yet, maybe I'll post a different new question.

Answer 1

Your argument is almost correct. You can’t use a fixed $b>10^7$, however: it’s possible that $a$ is the only element of $A$ in the set $\{a+kb:k\in\Bbb Z^+\}$. You can avoid this problem by arguing as follows.

Let $A_0=A$. Let $a_0=\min A_0$, let $B_0=\{a\in A:a\le a_0+10^7\}$, and let $A_1=A_0\setminus B_0$; by hypothesis $B_0$ is finite, so $A_1$ is non-empty, and we can let $a_1=\min A_1$.

In general, given an infinite multiset $A_n$, let $a_n=\min A_n$, let $B_n=\{a\in A:a\le a_n+10^7\}$, and let $A_{n+1}=A_n\setminus B_n$; $B_n$ is finite, so $A_{n+1}$ is infinite, and the recursive construction can continue.

In this way we find a sequence $\langle a_n:n\in\Bbb N\rangle$ in $A$ such that $a_n+10^7<a_{n+1}$ for each $n\in\Bbb N$. Clearly $\{a_n:n\in\Bbb N\}$ has no two elements within $10^7$ of each other.

Answer 2

Your idea is right, but your explanation of makes it a bit hard to see the crucial step. It can look a bit like you're having trouble explaining why there's always a $b$ to add, and is trying to make up for it by adding proofy-sounding fluff around it.

Here's how I would write basically the same idea:

We will prove the claim in contraposed form:

If there is no integer that appears infinitely many times (that is, every integer appears at most finitely many times), then we can choose infinitely many papers such that the difference of any two of those numbers will exceed $10^7$.

Namely, let $a_1$ be the smallest number on any of the papers, and construct a sequence $a_2, a_3, a_4, \ldots$ as follows:

For each $n$, let $a_{n+1}$ be the smallest number larger than $a_n+10^7$ that appears on any paper. There is always such a number, because each number less than this limit exists in only finitely many copies, so there are only finitely many papers with a number less than the limit. Since there are infinitely many papers, some of them must be above the limit.

This produces an infinite increasing sequence of numbers with a step size larger than $10^7$, so no two numbers in the sequence will be closer than that.

I don't think it would improve the presentation of the proof to phrase it such that the word "multiset" is mentioned -- even though multisets are of course one way to model the situation.