Two out of four
Four balls are arranged in a row, but they are not necessarily placed in the right order.
The problem is, you don't know what the correct order is.
If you are able to switch only two at a time, given the optimal strategy (where you want to minimize the total number of switches you make) what is the maximum number of switches you'd need to make before you are guaranteed that at least two are in the correct spot?
Image credit : depositphotos.com
The answer is 5.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Nice write up, David!
To state the "sufficient" part differently, if you do make all six permutations of A, B, and C, two are guaranteed to match at some point, since at least two of A, B, and C must be in the first 3 slots.
@David Vreken At first I was convinced about the "necessary" part of your argument, but now I'm not so sure... Can you explain a bit more why it works?
This makes me wonder if we can derive a general relationship, N ( m , n ) , where N is the number of switches needed to insure that m out of n balls match at some point.
In this case, N ( 2 , 4 ) = 5 . And, I believe that N ( 1 , n ) = n − 1 , and N ( n , n ) = n ! − 1 .
Log in to reply
Generalizing from this problem, it would also seem that N ( n − 2 , n ) = ( n − 1 ) ! − 1
Log in to reply
Ah yes.... True!
Log in to reply
@Geoff Pilling – Ah, David beat me to that one, but there is a discrepancy between N ( 1 , 3 ) = 3 − 1 = 2 by your formula, which is the correct value, and N ( 1 , 3 ) = ( 3 − 1 ) ! − 1 = 1 by David's formula, so the latter may only work for n > 3 . Your other observations look good, and clearly N ( n − 1 , n ) = N ( n , n ) . I'm also getting N ( 2 , 5 ) = 1 2 and N ( 2 , 6 ) = 1 3 . Full-sorting algorithms are well-documented but I'm finding it difficult to find references to this kind of partial sorting.
Log in to reply
@Brian Charlesworth – Actually, I believe N ( 1 , 3 ) = 1 . Start with ABC which covers sequences ABC, ACB, BAC, and CBA; then make 1 switch to BAC which covers the remaining sequences BCA and CAB.
What's interesting is that for all other values of n , it would appear that N ( 1 , n ) = n − 1 is correct.
Log in to reply
@David Vreken – Yeah, I agree. It does indeed look like N(1,3) = 1.
I wonder if some kind of recursion might work for the other numbers.
For example, if we know N(2,5), we can get an upper bound for N(3,6) of say 6*N(2,5) but are all those switches necessary?
Log in to reply
@Geoff Pilling – Yup, N ( 1 , 3 ) = 1 ; don't know what I was thinking. As David notes, it is interesting (weird) that n = 3 is the one exception to the N ( 1 , n ) formula. For N ( 2 , 5 ) my strategy was to first look at the first three elements, go through the 5 switches to see if any permutation yields two correct. If that doesn't pan out, then randomly swap in the other two elements, since we would then know that their proper positions are among the first three and hence guarantee that within 5 switches we will have two of the first three in the correct positions. The same for N ( 2 , 6 ) except we would need to swap in all three of the other elements first, resulting in one extra switch. Not sure if this is the most efficient strategy but at least it gives us an upper bound. The sequence 1 , 5 , 5 , 1 2 , 1 3 doesn't appear on OEIS though.
In general, recursion might work in forming upper bounds, but it seems like there may be no consistent maximum-efficiency sorting strategy for the various k , n in N ( k , n ) . As in the past, a problem of yours has opened a mathematical Pandora's box. :)
Log in to reply
@Brian Charlesworth – Hahaha... A Pandora's box! But only with people like you realizing the full potential of a problem, and stretching it far beyond it's original intent! :-)
@Brian Charlesworth – I've started a table summarizing what we've got so far...
1 2 3 4 5 6 1 0 n a n a n a n a n a 2 1 1 n a n a n a n a 3 1 5 5 n a n a n a 4 3 5 2 3 2 3 n a n a 5 4 1 2 ? 2 3 ? 1 1 9 1 1 9 n a 6 5 1 3 ? 1 1 9 ? 7 1 9 7 1 9 7 6 7 1 9 ? 5 0 3 9 8 7 5 0 3 9 ?
Look about right so far?
Log in to reply
@Geoff Pilling – Great format! Might need to change some of the N ( n − 1 , n ) entries so that they all equal N ( n , n ) , though.
Log in to reply
@Brian Charlesworth – Good eyes... Fixed!
Interesting that many of the solutions seem to be some factorial minus one.
@Brian Charlesworth – Clever solutions for N(2,5) and N(2,6)!
If I understood it right, does it prove that 12 and 13 are sufficient numbers of moves?
I wonder... Can we show somehow that 12 and 13 are also necessary?
Log in to reply
@Geoff Pilling – Yes, for N ( 2 , 5 ) I'm quite sure 12 switches are sufficient, but adapting David's necessity proof I believe that the least necessary number is 8, i.e., there are a maximum of 9 permutations of ABCDE no two of which have two balls in the same position, so 8 switches would be necessary. So there is potentially room for improvement on my method.
Let the balls be labelled A, B, C, and D.
Comparing any 2 of the 6 orderings ABCD, ACDB, ADBC, DACB, CABD, and BADC, there are no 2 balls in the same position, therefore, at least 6 different orders must be represented, or at least 5 switches are necessary.
To show that 5 switches are sufficient, the first 3 balls A, B, and C can be switched into all its permutations 3! - 1 = 5 times in the following order to cover all 24 possible orderings:
1) ABCD - covers orderings ABCD, ABDC, ACBD, ADCB, BACD, CBAD, and DBCA
2) ACBD - covers orderings ACDB, ADBC, BCAD, CABD, and DCBA
3) BCAD - covers orderings BCDA, BDAC, and DCAB
4) BACD - covers orderings BADC, BDCA, and DACB
5) CABD - covers orderings CADB, CDBA, and DABC
6) CBAD - covers orderings CBDA, CDAB, and DBAC
Therefore, 5 switches are necessary and sufficient to guarantee that at least two balls are in the correct spot.