The problem of the balls and the three boxes

Dr_Ochrome

New member
Joined
Sep 19, 2020
Messages
9
The exercise I'm going to present comes from my upper sixth mathematics book. It's the last exercise of the arithmetic exercise of that book and until now I neither succeeded to solve it nor found a good path. Here is the exercise

" We dispose of a number N of balls and three boxes so that each box can take at most the N balls. We distribute arbitrary the N balls in the three boxes.
The only operation allowed is to double the number of balls of one box by taking it from one of the two others.
Proof that whatever is the initial distribution of balls, it is always possible using the allowed operation described above to obtain an empty box. "

About my work, I tried to verify it through several examples and it was true, but i didn't find a way to proof it in general.
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
8,717
Please play by the rules of this site and show what you have done. Maybe we can point out something in your trials that can help you write up a valid proof.
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
10,593
The exercise I'm going to present comes from my upper sixth mathematics book. It's the last exercise of the arithmetic exercise of that book and until now I neither succeeded to solve it nor found a good path. Here is the exercise
" We dispose of a number N of balls and three boxes so that each box can take at most the N balls. We distribute arbitrary the N balls in the three boxes. The only operation allowed is to double the number of balls of one box by taking it from one of the two others.
Proof that whatever is the initial distribution of balls, it is always possible using the allowed operation described above to obtain an empty box. "
We can help you only if what you post makes sense. The above really makes little sense.
In counting theory, what I think you mean has a well known solution.
For example: If the three cells have no restrictions on the number of balls each can contain then,
the number of ways to place \(\bf N\) identical balls into \(\bf K\) different cells is \(\bf\dbinom {N+K-1}{N}\).
That formula is given to beginning students in combinatorics. It assumes that there is no maximum number in the cells nor does it consider if or if not a cell can be empty. Those considerations are studied in sections on occupancy: the study of Stirling Numbers.
Thus you need to repost your question(s). You need to clearly state exactly the question you are asking.
BTW: Why do you call yourself, Dr_Ochrome?
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
9,599
The exercise I'm going to present comes from my upper sixth mathematics book. It's the last exercise of the arithmetic exercise of that book and until now I neither succeeded to solve it nor found a good path. Here is the exercise

" We dispose of a number N of balls and three boxes so that each box can take at most the N balls. We distribute arbitrary the N balls in the three boxes.
The only operation allowed is to double the number of balls of one box by taking it from one of the two others.
Proof that whatever is the initial distribution of balls, it is always possible using the allowed operation described above to obtain an empty box. "

About my work, I tried to verify it through several examples and it was true, but i didn't find a way to proof it in general.
I would guess you have translated this from another language, not quite clearly. Here is my version of what I think it means:

We have N balls that are distributed in some way among three boxes, each of which is large enough to hold all of the balls. We are allowed to choose any box and move to it as many balls as that box contains from another box, thus doubling the number of balls in the one box and reducing the number in the second; we can repeat this as many times as we wish. Prove that, regardless of the initial distribution of balls, it is always possible to end up with one box empty.​

Please either confirm my interpretation or correct it; at several points I am departing from what you actually said.

I would start by "playing" with the idea for small N, to see if I could find a strategy to empty a box, as well as what might go wrong in trying to do so. (I haven't given any thought to it at all yet, as I don't want to waste time on a wrong interpretation; and my goal is just to suggest how one might approach it with no special knowledge, anyway.)

Now giving it a little thought, I see that one strategy may be to work backward from the goal, thinking about what must be true before the final step. You might even be able to show that starting with one box empty, you can reach any desired state by working backward.

May I also ask what topics were in that book that might be applicable? I presume it doesn't teach proof by induction ...
 

Dr_Ochrome

New member
Joined
Sep 19, 2020
Messages
9
I would guess you have translated this from another language, not quite clearly. Here is my version of what I think it means:

We have N balls that are distributed in some way among three boxes, each of which is large enough to hold all of the balls. We are allowed to choose any box and move to it as many balls as that box contains from another box, thus doubling the number of balls in the one box and reducing the number in the second; we can repeat this as many times as we wish. Prove that, regardless of the initial distribution of balls, it is always possible to end up with one box empty.​

Please either confirm my interpretation or correct it; at several points I am departing from what you actually said.

I would start by "playing" with the idea for small N, to see if I could find a strategy to empty a box, as well as what might go wrong in trying to do so. (I haven't given any thought to it at all yet, as I don't want to waste time on a wrong interpretation; and my goal is just to suggest how one might approach it with no special knowledge, anyway.)

Now giving it a little thought, I see that one strategy may be to work backward from the goal, thinking about what must be true before the final step. You might even be able to show that starting with one box empty, you can reach any desired state by working backward.

May I also ask what topics were in that book that might be applicable? I presume it doesn't teach proof by induction ...
So it was that obvious l was translating 😆. Your interpretation is correct. With a small N I succeeded to proof it buy taking some examples nothing more. I will try your idea about starting with an empty box and working backward to try to reach any desired state. The topic on that book where was the exercise was ARITHMETIC.
 

Dr_Ochrome

New member
Joined
Sep 19, 2020
Messages
9
Please play by the rules of this site and show what you have done. Maybe we can point out something in your trials that can help you write up a valid proof.
All l did is taking some examples to find a certain computing method which can be used whatever is the initial distribution. And l failed
 

Dr_Ochrome

New member
Joined
Sep 19, 2020
Messages
9
We can help you only if what you post makes sense. The above really makes little sense.
In counting theory, what I think you mean has a well known solution.
For example: If the three cells have no restrictions on the number of balls each can contain then,
the number of ways to place \(\bf N\) identical balls into \(\bf K\) different cells is \(\bf\dbinom {N+K-1}{N}\).
That formula is given to beginning students in combinatorics. It assumes that there is no maximum number in the cells nor does it consider if or if not a cell can be empty. Those considerations are studied in sections on occupancy: the study of Stirling Numbers.
Thus you need to repost your question(s). You need to clearly state exactly the question you are asking.
BTW: Why do you call yourself, Dr_Ochrome?
The interpretation of Dr Peterson about my exercise is right, it's what l meant in my post.
Why l called my self Dr_Ochrome? It doesn't means Doctor Ochrome cause l'm still a student. I heard that name somewhere, and i just wanted to put it as my nickname.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
9,599
So it was that obvious l was translating 😆. Your interpretation is correct. With a small N I succeeded to proof it buy taking some examples nothing more. I will try your idea about starting with an empty box and working backward to try to reach any desired state. The topic on that book where was the exercise was ARITHMETIC.
My main reason for asking about topics covered was that I don't think of proof as a topic at that level, so it could be helpful to know what sort of proving a student might be familiar with; that is, what would the student think "prove" means.

I'll start thinking more deeply about it, without going too deep!
 
Top