Does the game always end, regardless of the starting conditions?

[evinda]

We consider the game: for each integer $m$, there is infinite supply of balls marked with the number $m$. At the beginning, we are given a disk full of balls and we throw the balls of the disk , one from each integer , each time. If we throw a ball that is marked with $m$ , we can replace it with a finite number from balls marked with $1,2, \dots, m-1$ (so no replacement is getting done if we throw a ball marked with $1$). The game finishes, if the disk gets empty. We want to know if the game finishes, no matter which disk with balls will be given at the beginning.

I thought to show that the game finishes no matter which disk with balls will be given at the beginning, using induction on the maximum integer that appears at the balls that we throw.We symbolize the maximum integer that appears at the balls that we throw with $n$.

Base case: $n=1$. We throw a ball that is marked with $1$. From the hypothesis, no replacement is getting done if we throw a ball marked with $1$, so the game finishes.Induction hypothesis: Suppose that the game finishes when the maximum integer that appears at the balls that we throw is $n \geq 1$.

Induction step: We will show that the game finishes when the maximum integer that appears at the balls that we throw is $n+1$. We throw the ball that is marked with $n+1$ and then the maximum integer with which the ball, with which we could replace the ball that we just threw, could have is $n$. So from the induction hypothesis the game will end.

Thus, in any case the game will end.Is my induction right? Could I improve something at the formulation?How else could we show that the game will end in any case, without using induction?

 

[evinda]

I haven't understood if the game has just one round or more. Because it says that the game will end, if the disk gets empty... (Worried)

 

[I like Serena]

We consider the game: for each integer $m$, there is infinite supply of balls marked with the number $m$. At the beginning, we are given a disk full of balls and we throw the balls of the disk , one from each integer , each time. If we throw a ball that is marked with $m$ , we can replace it with a finite number from balls marked with $1,2, \dots, m-1$ (so no replacement is getting done if we throw a ball marked with $1$). The game finishes, if the disk gets empty. We want to know if the game finishes, no matter which disk with balls will be given at the beginning.

I thought to show that the game finishes no matter which disk with balls will be given at the beginning, using induction on the maximum integer that appears at the balls that we throw.We symbolize the maximum integer that appears at the balls that we throw with $n$.

Base case: $n=1$. We throw a ball that is marked with $1$. From the hypothesis, no replacement is getting done if we throw a ball marked with $1$, so the game finishes.Induction hypothesis: Suppose that the game finishes when the maximum integer that appears at the balls that we throw is $n \geq 1$.

Induction step: We will show that the game finishes when the maximum integer that appears at the balls that we throw is $n+1$. We throw the ball that is marked with $n+1$ and then the maximum integer with which the ball, with which we could replace the ball that we just threw, could have is $n$. So from the induction hypothesis the game will end.

Thus, in any case the game will end.Is my induction right? Could I improve something at the formulation?How else could we show that the game will end in any case, without using induction?

I haven't understood if the game has just one round or more. Because it says that the game will end, if the disk gets empty... (Worried)

Hey evinda! (Smile)

How many balls fit onto the disk?
And what happens if we remove a ball marked with $m$, but there are not enough empty spots to replace it with $1,...,m-1$?

If the highest integer that appears on the disk is $n=1$, it's not necessarily empty yet if we remove a ball, is it? (Wondering)

 

[evinda]

How many balls fit onto the disk?

It is not given but I think that we have to suppose that the disk has a finite number of balls, so that the game makes sense. (Thinking)

And what happens if we remove a ball marked with $m$, but there are not enough empty spots to replace it with $1,...,m-1$?

If there are no other balls to replace, aren't we at the next round and want to get rid of the balls marked with $m$, when the latter is the highest possible integer? Or have I understood it wrong? (Worried)

If the highest integer that appears on the disk is $n=1$, it's not necessarily empty yet if we remove a ball, is it? (Wondering)

No, we want to throw all the balls that are marked with $1$ and if there aren't any other available then the game ends, right? (Thinking)

 

[I like Serena]

It is not given but I think that we have to suppose that the disk has a finite number of balls, so that the game makes sense. (Thinking)

Okay, so the disk should have, say, $k$ places for balls, shouldn't it? (Wondering)

If there are no other balls to replace, aren't we at the next round and want to get rid of the balls marked with $m$, when the latter is the highest possible integer? Or have I understood it wrong? (Worried)

It's not given that we can choose which ball to pick, is it?
And I guess it's also not given how many balls we use to replace $m$ - only that they are lower numbered. (Thinking)

No, we want to throw all the balls that are marked with $1$ and if there aren't any other available then the game ends, right? (Thinking)

From the game description, we only throw off 1 ball at a time.
So I guess with $n=1$, we'll throw off 1 ball at a time until the disk is empty. (Thinking)

 

[evinda]

Okay, so the disk should have, say, $k$ places for balls, shouldn't it? (Wondering)

I assume so... (Thinking)

It's not given that we can choose which ball to pick, is it?
And I guess it's also not given how many balls we use to replace $m$ - only that they are lower numbered. (Thinking)

Right.

From the game description, we only throw off 1 ball at a time.
So I guess with $n=1$, we'll throw off 1 ball at a time until the disk is empty. (Thinking)

So the base case should be this: Let $n=1$, i.e. the highest integer with which the balls of the disk are marked is $1$. Since no replacement is geting done, we'll throw off 1 ball at a time until the disk is empty. We know that the disk will get empty and so that the game will end, since there are finite balls marked with $1$.

Right? Or could I improve somthing? (Thinking)

 

[I like Serena]

I assume so... (Thinking)

Right.

So the base case should be this: Let $n=1$, i.e. the highest integer with which the balls of the disk are marked is $1$. Since no replacement is geting done, we'll throw off 1 ball at a time until the disk is empty. We know that the disk will get empty and so that the game will end, since there are finite balls marked with $1$.

Right? Or could I improve somthing? (Thinking)

Sounds good. (Smile)

 

[evinda]

Sounds good. (Smile)

Nice (Smile)

At the induction hypothesis do we assume that when the highest integer with which the balls of the disk are marked is $n \geq 1$ the disk will always get empty and so the game will end?

 

[evinda]

If so, at the induction step which cases do we have to check? (Thinking)

 

[I like Serena]

Nice (Smile)

At the induction hypothesis do we assume that when the highest integer with which the balls of the disk are marked is $n \geq 1$ the disk will always get empty and so the game will end?

If so, at the induction step which cases do we have to check? (Thinking)

How about supposing there are $j \ge 1$ balls marked with $n+1$ on the disk. (Thinking)

 

[evinda]

How about supposing there are $j \ge 1$ balls marked with $n+1$ on the disk. (Thinking)

So we do a second induction at the induction step, right?

I have tried the following:

We want to show that when the highest integer with which the balls of the disk are marked is $n+1$ the disk will always get empty and so the game will end. Suppose that there are $j \geq 1$ balls marked with $n+1$ on the disk.

We will show that the game will end by using induction on $j$.

Base case 2: Let $j=1$. Then we throw the only ball marked with $n+1$ and then we can replace it with a finite number of balls marked with $1,2, \dots, n-1$. From the induction hypothesis we know that the game will end.

Induction hypothesis 2: We suppose that the game will end when there are $m \geq 1$ balls marked with $n+1$.

Induction step 2: We will show that the game will end when there are $m+1$ balls marked with $n+1$.
We throw a ball marked with $n+1$ and then we can replace it with a finite number of balls marked with $1,2, \dots, n$. Then there remain $m$ balls marked with $n+1$ and from the induction hypothesis 2, we deduce that the game will end.Am I right? Could I improve something? (Thinking)

 

[I like Serena]

Base case 2: Let $j=1$. Then we throw the only ball marked with $n+1$ and then we can replace it with a finite number of balls marked with $1,2, \dots, n-1$. From the induction hypothesis we know that the game will end.

I thought we couldn't "choose" the ball marked with $n+1$.

Instead we would either pick the ball marked with $n+1$ and continue as outlined, or we'd pick a different ball.
Suppose we would postpone the $n+1$ ball as long as possible, then according to the previous induction hypothesis, it would take at most, say $f(n)$ moves before the disk is empty except for the $n+1$ ball.
Then we'd have to pick the $n+1$ ball and replace it with lower numbered balls, after which it will take at most $f(n)$ moves before the disk is completely empty.
In other words, it will take at most $f(n) + 1 + f(n)$ moves before the disk is empty, and we can freely choose when to pick the $n+1$ ball.
When the disk is empty the game will indeed end.

We might say that $f_{j=1}(n+1) = f_{k-1}(n) + 1 + f_{k}(n)$, where $k$ is the size of the disk, and $f_j(m)$ is an upper bound for the number of moves before the game ends when the highest numbered ball is $m$ and there are at most $j$ balls marked $m$. (Thinking)

 

[evinda]

I thought we couldn't "choose" the ball marked with $n+1$.

Instead we would either pick the ball marked with $n+1$ and continue as outlined, or we'd pick a different ball.
Suppose we would postpone the $n+1$ ball as long as possible, then according to the previous induction hypothesis, it would take at most, say $f(n)$ moves before the disk is empty except for the $n+1$ ball.
Then we'd have to pick the $n+1$ ball and replace it with lower numbered balls, after which it will take at most $f(n)$ moves before the disk is completely empty.

I am a little confused right now... (Worried) Postponing the $n+1$ ball, the disk gets empty except for the $n+1$ ball. Then taking the $n+1$ ball, we are talking about the next round. But then why do we know that we don't need another round for the balls marked with $1, \dots, n$ ? (Sweating)

 

[I like Serena]

I am a little confused right now... (Worried) Postponing the $n+1$ ball, the disk gets empty except for the $n+1$ ball. Then taking the $n+1$ ball, we are talking about the next round. But then why do we know that we don't need another round for the balls marked with $1, \dots, n$ ? (Sweating)

What do you mean by a "round"? (Wondering)

The $n+1$ ball is taken at some indeterminate time. Something between the first and the last ball to take.
But at most $f(n)$ balls can be taken before, and at most $f(n)$ balls can be taken after. (Thinking)

 

[evinda]

What do you mean by a "round"? (Wondering)

The $n+1$ ball is taken at some indeterminate time. Something between the first and the last ball to take.

Why? If we throw a ball marked with $m$, we can replace it with a finite number of balls marked with $1, \dots, m-1$... (Worried)

I still haven't understood it. (Sweating)

 

[evinda]

Suppose we would postpone the $n+1$ ball as long as possible, then according to the previous induction hypothesis, it would take at most, say $f(n)$ moves before the disk is empty except for the $n+1$ ball.
Then we'd have to pick the $n+1$ ball and replace it with lower numbered balls, after which it will take at most $f(n)$ moves before the disk is completely empty.

But having postponed the $n+1$ ball, the highest integer with which the balls were marked was $n$ and so from the induction hypothesis ignoring the $n+1$ ball, the disk would get empty. So the only remaining ball is the $n+1$ ball, but we cannot replace it with lower numbered balls and so the game will end. Or have I understood it wrong? (Sweating)

 

[I like Serena]

Why? If we throw a ball marked with $m$, we can replace it with a finite number of balls marked with $1, \dots, m-1$... (Worried)

I still haven't understood it. (Sweating)

We have to prove that the game will end regardless of when any ball is thrown and replaced.
If the $n+1$ ball is thrown first, we have to prove the game will end.
If the $n+1$ ball is thrown last, we have to prove the game will end.
And if it is thrown at any time in between, we still need to ensure the game will end. (Thinking)

But having postponed the $n+1$ ball, the highest integer with which the balls were marked was $n$ and so from the induction hypothesis ignoring the $n+1$ ball, the disk would get empty. So the only remaining ball is the $n+1$ ball, but we cannot replace it with lower numbered balls and so the game will end. Or have I understood it wrong? (Sweating)

Don't we have an infinite supply of any numbered balls? (Wondering)
So when we get around to throwing the $n+1$ ball we can replace it with presumably any number of lower numbered balls - as long as they fit on the disk.
It seems we don't even know how many of each, other than that there is an upper bound to the total number.

 

[evinda]

We have to prove that the game will end regardless of when any ball is thrown and replaced.
If the $n+1$ ball is thrown first, we have to prove the game will end.
If the $n+1$ ball is thrown last, we have to prove the game will end.
And if it is thrown at any time in between, we still need to ensure the game will end. (Thinking)

So, if the $n+1$ ball is thrown first, then the highest integer that appears at the balls of the disk is $n$ and so we know from the induction hypothesis that the game will end.

If the $n+1$ ball is thrown last, before this step, the highest integer that appeared at the balls of the disk was $n$ so after having thrown them in finite time because of the induction hypothesis, the disk will finally only contain the $n+1$ ball , we will throw it and then the disk will be empty and so the game will end.

If the $n+1$ ball is thrown in any time between , then before the $n+1$ ball is thrown, the highest integer was $n$ and so from the induction hypothesis the disk would get empty, then we would throw the $n+1$ ball, and then the highest integer that appears at the balls of the disk is $n$ and so we know from the induction hypothesis that the game will end.

Right?

 

[I like Serena]

So, if the $n+1$ ball is thrown first, then the highest integer that appears at the balls of the disk is $n$ and so we know from the induction hypothesis that the game will end.

If the $n+1$ ball is thrown last, before this step, the highest integer that appeared at the balls of the disk was $n$ so after having thrown them in finite time because of the induction hypothesis, the disk will finally only contain the $n+1$ ball , we will throw it and then the disk will be empty and so the game will end.

If the $n+1$ ball is thrown in any time between , then before the $n+1$ ball is thrown, the highest integer was $n$ and so from the induction hypothesis the disk would get empty, then we would throw the $n+1$ ball, and then the highest integer that appears at the balls of the disk is $n$ and so we know from the induction hypothesis that the game will end.

Right?

Yep. Except that if $n+1$ is the last ball, the disk won't be empty yet would it? (Wondering)

 

[evinda]

Yep. Except that if $n+1$ is the last ball, the disk won't be empty yet would it? (Wondering)

Why? Before we throw the $n+1$ ball we will get rid all the balls numbered with $1, 2, \dots, n$.
Then will we take again balls numbered with $1, 2, \dots, n$ since there is an infinite supply of them?Does this also hold at the case when the $n+1$ ball is thrown in any time?

 

[I like Serena]

Why? Before we throw the $n+1$ ball we will get rid all the balls numbered with $1, 2, \dots, n$.
Then will we take again balls numbered with $1, 2, \dots, n$ since there is an infinite supply of them?

Does this also hold at the case when the $n+1$ ball is thrown in any time?

As I understand it, when we throw the $n+1$ ball off last, we still have to replace it in some unspecified fashion with a finite number of balls numbered $1, ..., n$, which then have to be thrown off again.
If the $n+1$ ball is thrown off earlier, the situation is completely the same - we still have balls up to $n$.

 

[evinda]

Ah I understand now what you mean.

So the base case 2 will be the following, right?

Let $j=1$. We could either throw at the beginning the $n+1$ ball and then the highest integer will be $n$ and so from the induction hypothesis the game will end or we could pick firstly a different ball.
By postponing the $n+1$ ball as long as possible, according to the induction hypothesis, it would take at most, say $f(n)<+\infty$ moves before the disk is empty except for the $n+1$ ball.
Then we'd have to pick the $n+1$ ball and replace it with lower numbered balls, after which it will take at most $f(n)$ moves before the disk is completely empty.
In other words, it will take at most $f(n) + 1 + f(n)$ moves before the disk is empty, and we can freely choose when to pick the $n+1$ ball.
When the disk is empty the game will indeed end.And at the induction hypothesis 2 , we suppose that the game will end when there are $j \geq 1$ balls marked with $n+1$, right?

 

[I like Serena]

Ah I understand now what you mean.

So the base case 2 will be the following, right?

Let $j=1$. We could either throw at the beginning the $n+1$ ball and then the highest integer will be $n$ and so from the induction hypothesis the game will end or we could pick firstly a different ball.
By postponing the $n+1$ ball as long as possible, according to the induction hypothesis, it would take at most, say $f(n)<+\infty$ moves before the disk is empty except for the $n+1$ ball.
Then we'd have to pick the $n+1$ ball and replace it with lower numbered balls, after which it will take at most $f(n)$ moves before the disk is completely empty.
In other words, it will take at most $f(n) + 1 + f(n)$ moves before the disk is empty, and we can freely choose when to pick the $n+1$ ball.
When the disk is empty the game will indeed end.

I think it should be "By throwing the $n+1$ ball off later" instead of "By postponing the $n+1$ ball as long as possible". (Thinking)

And at the induction hypothesis 2 , we suppose that the game will end when there are $j \geq 1$ balls marked with $n+1$, right?

Yep. (Nod)

 

[evinda]

Then at the induction step, we want to show that the game will end when there are $j+1$ balls marked with $n+1$.

There are two possible cases.

We throw firstly a ball marked with $n+1$ and replace it with lower numered balls. Then there remain $j$ balls marked with $n+1$. From the second induction hypothesis, we know that the game will end.

By throwing the first $n+1$ ball later, from the first induction hypothesis we know that the disk will get empty after a finite number of moves, except for the $n+1$ balls. One time, we throw a $n+1$ ball, we replace it with lower numbered balls and then we know, from the second induction hypothesis that the game will end.Is it right? Could I improve somthing? Do we have to justify why we have to throw after some time a $n+1$ ball?

 

[I like Serena]

Then at the induction step, we want to show that the game will end when there are $j+1$ balls marked with $n+1$.

There are two possible cases.

We throw firstly a ball marked with $n+1$ and replace it with lower numered balls. Then there remain $j$ balls marked with $n+1$. From the second induction hypothesis, we know that the game will end.

By throwing the first $n+1$ ball later, from the first induction hypothesis we know that the disk will get empty after a finite number of moves, except for the $n+1$ balls. One time, we throw a $n+1$ ball, we replace it with lower numbered balls and then we know, from the second induction hypothesis that the game will end.Is it right? Could I improve somthing? Do we have to justify why we have to throw after some time a $n+1$ ball?

It looks fine to me. (Nod)

 

[evinda]

It looks fine to me. (Nod)

Great... Thank you! (Smirk)