Author |
Topic: Swapping 2n balls in n bins (Read 600 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Swapping 2n balls in n bins
« on: Nov 24th, 2005, 4:30pm » |
 Quote  Modify
|
You are given n bins, labelled in order 1,2,...,n. Bin 'k' contains two balls, both labelled 'n-k+1'. If you can only swap balls between adjacent bins (one from each bin), what is the minimum number of swaps needed to get the balls in the right bins?
For example, when n=5, we wish to go from
(1,1) (2,2) (3,3) (4,4) (5,5)
to
(5,5) (4,4) (3,3) (2,2) (1,1).
|
| « Last Edit: Nov 26th, 2005, 12:28pm by Eigenray » |
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Swapping 2n balls in n bins
« Reply #1 on: Nov 24th, 2005, 7:37pm » |
Quote Modify
|
If I am reading this correctly, what is the point of having two balls in each bin? If you can only swap pairs of balls, the two balls in each bin always stay together, and could be treated as a single ball.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Swapping 2n balls in n bins
« Reply #2 on: Nov 24th, 2005, 10:05pm » |
Quote Modify
|
Okay that wasn't phrased well. I mean you can only swap two balls at a time: one from bin k with one from bin k+1.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Swapping 2n balls in n bins
« Reply #3 on: Nov 26th, 2005, 1:55am » |
Quote Modify
|
on Nov 24th, 2005, 4:30pm, Eigenray wrote:| You are given n bins, labelled in order 1,2,...,n. Bin 'k' contains two balls, both labelled 'n+k-1'. |
|
You mean bin 'k' contains two balls, each labelled 'n-k+1' ?
I guess an upper bound to S(n), the minimum number of swaps required, is S(n) <= n(n - 1).
|
| « Last Edit: Nov 26th, 2005, 2:10am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Swapping 2n balls in n bins
« Reply #4 on: Nov 26th, 2005, 4:46am » |
Quote Modify
|
Obviously, one can do better than the upper bound indicates. For n=3, a greedy algorithm (always swap two balls that are wrongly ordered and that carry labels with maximum difference) leads to a total of 5 swaps (one less than the upper bound):
3,3 / 2,2 / 1,1
3,3 / 1,2 / 1,2
1,3 / 3,2 / 1,2
1,3 / 1,2 / 3,2
1,1 / 3,2 / 3,2
1,1 / 2,2 / 3,3
|
| « Last Edit: Nov 26th, 2005, 4:47am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Swapping 2n balls in n bins
« Reply #5 on: Nov 26th, 2005, 1:05pm » |
Quote Modify
|
Yes. In fact that is optimal for n=3.
It's a bit counter-intuitive. My first impression was that it "obviously" takes twice as many swaps than the case of 1 ball in each bin.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Swapping 2n balls in n bins
« Reply #6 on: Nov 26th, 2005, 1:49pm » |
Quote Modify
|
You can get a better lower bound by counting the number of pairs of balls that are misordered - that is, two balls are labelled m and n with m > n, but ball m is to the left of ball n. At the start, there are 4 C(n, 2) = 2n (n - 1) misorderings. Any swap can change remove at most 3 misorderings: the two balls that are swapped, the ball on the left with the other ball on the right, and the ball on the right with the other ball on the left. So to get the number of misorderings down to zero requires at lesast Ceil [2n (n - 1) / 3] swaps.
In addition, note that when the second ball labelled n is placed in its proper position, we don't get to reduce by 3; the two balls labelled n were not considered misordred originally. So we lose a reduction for each number 1 to n, and our lower bound increases to Ceil [(2n2 - n) / 3].
This bound is sharp for 2 <= n <= 5; for these cases, a simple strategy is to move a ball labelled n and a ball labelled 1 next to each other near the center. Then you just start shifting the balls to their correct places, starting from the extremes and working your way in, each time shifting with the more misplaced ball. The first step takes n - 2 swaps, and these are 'bad swaps' according to Jock's [n2 / 2] formula; they reduce one ball's misallocation by one, but increase the other by one, so the function stays the same. Every swap after that is a 'good swap' - both balls have the misallocation reduced by one - so we reach the desired position in [n2 / 2] + n - 2 steps (which coincidentally, matches up with the previous formula for 2 <= n <= 6!)
For example, take n = 5:
5 4 3 2 1
5 4 3 2 1
The first step brings 5 and 1 together.
4 3 5 1 2
5 4 3 2 1
These are the three 'bad swaps'. Next we move 5 all the way to the right; the 'most misallocated' balls to swap with are the two 1's, so those are swapped.
4 3 1 1 2
5 4 3 2 5
Next we move the 1's all the way to the left, this time choosing the largest number to swap from each time.
4 3 4 1 2
1 5 3 2 5
1 3 5 4 2
1 4 3 2 5
Next we swap the 5 and left 4 with the 2's and one more swap of 3 and 2 finishes it. That's 15 swaps, 3 bad and 12 good, and that matches both formulas.
But it doesn't quite work for n = 6. Using the strategy above, after first 1 and 6 are placed, we wind up needing to use one more bad swap to keep going, so we need to use 23 swaps rather than the 22 that both formulas give us. (I haven't proven that 23 is required, though) Perhaps the required number is asymptotic with n2 after all.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Swapping 2n balls in n bins
« Reply #7 on: Nov 26th, 2005, 3:13pm » |
Quote Modify
|
Increasing the number of balls per bin from one to two, you need more swaps but in general not twice as many. For large number of bins you need about 50% more swaps.
However, I have not yet managed to figure out a general equation for the number of swaps required.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Swapping 2n balls in n bins
« Reply #8 on: Nov 26th, 2005, 3:18pm » |
Quote Modify
|
Do you see a flaw with my lower bound?
EDIT: just realized that 50% more is more than my lower bound - got confused for a second.
|
| « Last Edit: Nov 26th, 2005, 3:32pm by Deedlit » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Swapping 2n balls in n bins
« Reply #9 on: Nov 27th, 2005, 1:40am » |
Quote Modify
|
Yes, so far all results are mutually compatible.
In fact, we can generalise to k times n balls in n bins. The required number of swaps S(k,n) is bounded by generalising my upper bound and your lower bound to arbitrary k>0:
Ceil((k2n(n-1)/2 + (k-1)n)/(2k-1)) <= S(k,n) <= nk(n-1)/2
Obviously, for k=1 both bounds coincide, whilst for arbitrary n and k the ratio between the upper and the lower bound never exceeds (2k - 1)/k.
Asymptotically, S(n,k) = Ck n2 + O(n) with: k2/(4k-2) <= Ck <= k/2
|
| « Last Edit: Nov 27th, 2005, 2:23am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print