Unbounded finite processes

[bonanova]

I was reading about processes that have an unbounded number of steps but a certain conclusion. It interested me because I had associated unboundedness with for example the counting numbers. Give me an integer as large as you like and there is an integer that is one higher. More dramatically, for every integer N, no matter how large, it can be dwarfed by the integer N raised to the Nth power. I intuitively took this to be a description, informal perhaps, of Aleph null.

The process that was being discussed can be described as follows.

You are given a bucket that contains an arbitrarily large number of balls, numbered 1-N, and you are to empty it by a series of steps described below.. For each ball number there is supplied another bucket with an infinite number of balls with the same number. That is, if the original bucket contains a ball that is numbered 3, there is another bucket with an infinite number of balls also numbered 3. You then proceed as follows. A ball of your choosing, say its number is p, is removed from the original bucket and discarded. The second part of the step is that an arbitrarily large number of balls numbered p-1 are taken from the infinite bucket of p-1 balls and put into the original bucket. Each replacement could entail adding to the bucket a set of new balls of size equal to the number of electrons in the universe. Nevertheless, the process ultimately terminates because when you remove a ball that has the number 1 on it, you don't replace it with any other balls.

The interesting fact about this procedure is that at no point, at least until only balls that are numbered with a 1 remain in the bucket, is it possible to give an upper bound for the number of steps remaining to completion. Yet completion is guaranteed. The number is steps is unbounded - give me a number of steps and I will ensure the process goes longer - yet finite.

So my thought was, is it a sufficient argument, to prove the integers are infinite, simply to say that no matter how large an integer you choose I will give you one that is larger?
_________________
_{Vidi, vici, veni.}

[Thok]

[bonanova]

I agree. I was intrigued with an unbounded process that would always come to completion. But it's the fact that at every point it stays finite that matters.
_________________
_{Vidi, vici, veni.}

[L'lanmal]

Here is a twist which, in a different context, blew my mind once.

Let's add a second option... after drawing a ball, you can put it back, leaving the bucket's state unchanged.

Then the process is no longer guaranteed to terminate, and the number of balls the bucket can contain is unbounded. And you can go an arbitrary amount of time with the same number of balls in the bucket only to jump up by a few million later.

Yet the number of balls in the bucket will converge. *Edit: to make the statement make sense, I guess I also need to say that if you have an empty bucket you must leave it unchanged.

(In short, either you get in an infinite loop of replacing the last ball you drew, or you don't. If you do, you have converged to the number at that point. If you don't, it eventually terminates with 0.)

[Griffin]

*wanders in*

bonanova, your unbounded process reminds me of a Putnam problem:

Show that every rational number can be written as the quotient of products of factorials of (not necessarily distinct) primes. For example,

10/9 = (5! 2!)/(3! 3! 3!)

*wanders out*

[novice]

[Griffin]

Nice novice! And I suppose I meant positive rational number, but if we allow a negative sign all is well.

bonanova's post reminded me of this problem since in step b) when showing X = (n+1) can be written in this way, we need that n! can be written in this way. To get that, we need to apply the induction hypothesis for a whole lot of different values, but since each time is for a smaller value than X, the process eventually terminates.