Simple, almost "intuitive" conjecture, hard or impossible to solve?

  • I
  • Thread starter fluidistic
  • Start date
  • #1
fluidistic
Gold Member
3,671
110

Main Question or Discussion Point

Hello,
I have posted a problem (on math stack exchange) I was given for fun by an uncle, who doesn't know whether the proof is possible to establish. I tried my best and failed so far. I don't think I can solve the problem with my current knowledge and I would love to know if you can find a solution or at least have some ideas.
Problem statement:
There are initially three boxes, labelled ##A##, ##B## and ##C##. ##A## contains ##3n## balls, with ##n\geq 5## a natural number. At step number ##k##, one withdraws ##k## balls from any box and place it into any other box. Show that it is always possible to end up with ##n## balls in each boxes after exactly ##n## steps.
So far I have been able to show that there is no possible proof by induction, I believe. The reasoning is that if we start with a solution that works for ##n## steps, then we cannot make any further step because it would mean to withdraw ##n+1## balls from any box, making the number of balls negative in that box, which is not allowed.
So maybe number theory can offer a way to tackle the problem?

I have written a Python program that outputs the solutions for a given ##n##, and I have stared hard at them (their number grows quite quickly with ##n##. There are 36 or 72 solutions for ##n=9## for instance, starting from 1 or 2 solutions for n=5 depending on whether ##B## and ##C## are distinguishable). No luck, I couldn't notice obvious patterns or ways to create solutions. Some of them look almost trivial (i.e. withdraw balls from box A most of the time and place them into either ##B## or ##C## and then at the final step(s) withdraw from ##B## into ##C## or the opposite) but in general there is no such "trivial looking" solution. So I am not able to find an algorithmic or automatic way to build a solution from scratch.
 
  • Like
Likes mfb

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,179
1,316
An algebra lovers version of the problem:

Let ##T_k = (\frac{A^k}{B^k} + \frac{B^k}{A^k} + \frac{A^k}{C^k} + \frac{C^k}{A^k} + \frac{B^k}{C^k} + \frac{C^k}{B^k} )##

If ##n \ge 5## must the product ##A^{3n} \prod_{k=1}^n T_k ## contain a term of the form ##A^nB^nC^n## ?
 
  • Like
Likes mfb
  • #3
1,752
819
this kind of problem is way beyond me. I did have an idea though. What if you think backwards -- you start with n balls in each box, and move n, then n-1... to end up with all balls in box 1.
 
  • #4
34,390
10,476
An algebra lovers version of the problem:

Let ##T_k = (\frac{A^k}{B^k} + \frac{B^k}{A^k} + \frac{A^k}{C^k} + \frac{C^k}{A^k} + \frac{B^k}{C^k} + \frac{C^k}{B^k} )##

If ##n \ge 5## must the product ##A^{3n} \prod_{k=1}^n T_k ## contain a term of the form ##A^nB^nC^n## ?
Are you sure this avoids problems with negative numbers? As an example, if you want to move 1 ball with steps 1 and 2 then simple algebra tells you that -1+2=1, you could do that - but in practice you cannot, because you can't leave -1 balls then add 2 to get 1 ball.
 
  • #5
Stephen Tashi
Science Advisor
7,179
1,316
I would love to know if you can find a solution or at least have some ideas.
So far I have been able to show that there is no possible proof by induction, I believe.
You only tried a weak form of induction. There are techniques called "strong induction".

Some ideas:

If a solution exists for ##3n## balls, then after step ##n-1## we had a situation where the occupancy numbers were ##\{2n,n,0\}## (in some order).

Consder the case of ##3(n+1) = 3n+3## balls. Let ##w = n-r ## for some ##r## such that ## w \ge 5##. After step ##n-r -1= w-1## we could have arrived at the occupancy numbers ## \{2(w) + (3n+3 - 3w) , w, 0\}##
We can do this by pretending we are solving the problem for the case of ##3w## balls (i.e. for the initial occupancy numbers ##\{3w,0,0\}##) Using that solution we distribute ##3w## balls and have ## (3n+3 - 3w) ## balls "left over" in the box where they began.

This opens up the idea of assuming we begin with the situation ##\{ 2(w) + (3n+3 -3w), w, 0 \}## at step ##n-r-1## and trying to show we can reach the numbers ## \{2(n+1), n+1, 0\}## at step ##n##. (Thus showing we can reach ##\{n+1,n+1,n+1\} ## at step ##n+1##).

I don't know whether this can be proven. I'd begin by looking at your numerical examples to see if any of the solutions are examples of the above technique. For example, would the first 5 steps of some solution for the case of 10 balls constitute a solution for 5 balls.

When looking for patterns in the solutions, don't look only at the number of balls in the boxes in each step. Also look at the sequences of numbers of balls that are added and subtracted in each step. Do any sequences for larger numbers of balls contain sequences for smaller numbers of balls embedded in them? Write the data in some way that different orders of the boxes doesn't matter. For example, instead of listing the numbers of balls in boxes A,B,C in the order of the boxes, list the numbers of balls in the boxes from largest number to smallest number. Instead of listing the number of balls removed and added in the order of boxes, list those numbers in the order of the numbers of balls initially in the boxes. For example, (-3,3,0) to indicate removing 3 balls from the box with he largest number of balls and putting them in the box with the second largest number of balls.
 
  • #6
fluidistic
Gold Member
3,671
110
The problem has apparently been solved (via a way) in the math exchange website linked above, for anyone interested.
 
  • Informative
Likes mfb

Related Threads on Simple, almost "intuitive" conjecture, hard or impossible to solve?

  • Last Post
Replies
20
Views
22K
Replies
2
Views
546
Replies
8
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
6
Views
4K
  • Last Post
Replies
9
Views
10K
Replies
7
Views
2K
  • Last Post
Replies
1
Views
14K
Replies
1
Views
987
Top