22.12.2019, 17:45
My friend Dmitry Borisenkov, who is also participating in the contest, sent me his 'human' proof of solution.
-----------------------------------------
I do not have a mathematical proof of the algorithm I propose, but I believe it works.
I'll try to explain this algorithm.
Unfortunately, I didn't write a program to test it.
I can write this program, but not right now.
As a preface, it is not too complicated to prove that we always can sort:
any 4 or less balls (or two separate pairs) in 1 step;
any 5 balls in 2 steps (except if none of them were previously compared but this is not our case);
any 6 balls in 3 steps (and sometimes in 2 steps if some of them are already sorted but it should be proven);
any 7 balls in 4 steps (and sometimes in 3 steps but it should be proven);
any 8 balls in 5 steps (and sometimes in 4 steps but it should be proven).
We can sometimes sort 9 balls in 5 steps but it should be proven.
Sorting 12 balls in 10 steps (what I think is not a minimal possible step count) is relatively simple, e.g.:
1-5) sort any 8 balls:
1-2) sort two separate fours;
3) take the two heaviest balls from each four and select the two heaviest of the eight;
4) take the two next heaviest balls from each four and select the two next heaviest of the eight;
5) sort the remaining four;
6-7) we have 8 sorted balls now, e.g. A1 > A2 > A3 > A4 > A5 > A6 > A7 > A8.
In the 6th and 7th weighings compare A3 and A6 with two separate remaining pairs;
8-10) we have to sort 6 balls, or 5 + 3 balls, or 4 + 4 balls, or 4 + 3 + 3 balls.
Everything can be done in 3 weighings.
Sorting 12 balls in 9 steps is more complicated, so let's try the following:
1) sort any four balls: A1 > A2 > A3 > A4.
2) sort A2 (A3 also fits) with three balls that are unsorted yet. There can be 4 cases:
a) A2 > B1 > B2 > B3
b) B1 > A2 > B2 > B3
c) B1 > B2 > A2 > B3
d) B1 > B2 > B3 > A2
3) A2 is now the dividing ball (we can say about it that it is heavier or lighter than any ball that was already weighed).
The aim of the algorithm is to always have a dividing ball and it is better that the two counts of balls heavier and lighter than the dividing ball were as close to each other as possible.
Now on the 3rd step we want to sort two balls nearest in weight to the dividing ball (on the side where the count of balls is greater) with two balls unsorted yet.
The aim is to have the dividing ball nearer to the middle of all weighed balls.
in case a) weigh A3 and B1 with two balls that are unsorted yet;
in case b) weigh A3 and B2 with two balls that are unsorted yet;
in case c) weigh A3 and B3 (A1 and B2 also fit) with two balls that are unsorted yet;
in case d) weigh A1 and B3 with two balls that are unsorted yet.
4) we now have a dividing ball again (it can be still A2 or another ball, but it always exists - I didn't prove it, but I listed all the cases).
If more than one ball can be taken as the dividing ball, take the ball nearest to the middle of all balls already weighed.
Sort the dividing ball with three last balls unsorted yet.
After the 4th step we have a directed graph of 12 sorted balls. The ball that was dividing on the previous step is still the dividing ball.
Now we have to sort N balls that are heavier than the dividing ball and M balls that are lighter than it.
N = 4, M = 7 or M = 4, N = 7 - no problem, we can always do it in 1+4 = 5 steps, total step count is <= 9;
N = 5, M = 6 or M = 6, N = 5 - no problem, we can always do it in 2+3 = 5 steps, total step count is <= 9;
two other remaining cases are to be investigated
N = 3, M = 8 or N = 8, M = 3
N = 2 (sorted), M = 9 or N = 9, M = 2 (sorted)
other cases are impossible (N <=1, or N >= 10, or N/M = 2 and these two are unsorted are all prevented by the previous actions).
I think we can always sort 9 balls or 3 + 8 balls in 5 steps after the steps 1-4 because 9 or 8 balls are already split into sorted (or partially sorted) groups.
Sorting 2 remaining balls in a group of 3 can be done in the same step as sorting some 2 balls in a group of 8.
E.g., let's consider a case 9 = 3 + 3 + 2 + 1, balls in each group more than one ball (3, 3 and 2) are already sorted.
1) weigh the heaviest balls of each group, select the heaviest ball of 9;
2) weigh the lightest balls of each group, select the lightest ball of 9;
3) only 2 balls can be the second heaviest now and only 2 balls can be the second lightest.
Weigh these four balls, and we know the two heaviest balls and the two lightest balls of 9.
4-5) Sort remaining 5 balls. We did it in 5 steps, 5+4=9, it is OK.
I looked through all the cases and I saw that it can be done.
It would take a lot of time and space to write it there.
I'm not absolutely sure that I'm right and my calculations don't contain errors.
But I can bet some amount of money (e.g., 20 Euros) on my solution :-)
I also think that 8 steps are insufficient to sort 12 balls.
-----------------------------------------------------------------------
-----------------------------------------
I do not have a mathematical proof of the algorithm I propose, but I believe it works.
I'll try to explain this algorithm.
Unfortunately, I didn't write a program to test it.
I can write this program, but not right now.
As a preface, it is not too complicated to prove that we always can sort:
any 4 or less balls (or two separate pairs) in 1 step;
any 5 balls in 2 steps (except if none of them were previously compared but this is not our case);
any 6 balls in 3 steps (and sometimes in 2 steps if some of them are already sorted but it should be proven);
any 7 balls in 4 steps (and sometimes in 3 steps but it should be proven);
any 8 balls in 5 steps (and sometimes in 4 steps but it should be proven).
We can sometimes sort 9 balls in 5 steps but it should be proven.
Sorting 12 balls in 10 steps (what I think is not a minimal possible step count) is relatively simple, e.g.:
1-5) sort any 8 balls:
1-2) sort two separate fours;
3) take the two heaviest balls from each four and select the two heaviest of the eight;
4) take the two next heaviest balls from each four and select the two next heaviest of the eight;
5) sort the remaining four;
6-7) we have 8 sorted balls now, e.g. A1 > A2 > A3 > A4 > A5 > A6 > A7 > A8.
In the 6th and 7th weighings compare A3 and A6 with two separate remaining pairs;
8-10) we have to sort 6 balls, or 5 + 3 balls, or 4 + 4 balls, or 4 + 3 + 3 balls.
Everything can be done in 3 weighings.
Sorting 12 balls in 9 steps is more complicated, so let's try the following:
1) sort any four balls: A1 > A2 > A3 > A4.
2) sort A2 (A3 also fits) with three balls that are unsorted yet. There can be 4 cases:
a) A2 > B1 > B2 > B3
b) B1 > A2 > B2 > B3
c) B1 > B2 > A2 > B3
d) B1 > B2 > B3 > A2
3) A2 is now the dividing ball (we can say about it that it is heavier or lighter than any ball that was already weighed).
The aim of the algorithm is to always have a dividing ball and it is better that the two counts of balls heavier and lighter than the dividing ball were as close to each other as possible.
Now on the 3rd step we want to sort two balls nearest in weight to the dividing ball (on the side where the count of balls is greater) with two balls unsorted yet.
The aim is to have the dividing ball nearer to the middle of all weighed balls.
in case a) weigh A3 and B1 with two balls that are unsorted yet;
in case b) weigh A3 and B2 with two balls that are unsorted yet;
in case c) weigh A3 and B3 (A1 and B2 also fit) with two balls that are unsorted yet;
in case d) weigh A1 and B3 with two balls that are unsorted yet.
4) we now have a dividing ball again (it can be still A2 or another ball, but it always exists - I didn't prove it, but I listed all the cases).
If more than one ball can be taken as the dividing ball, take the ball nearest to the middle of all balls already weighed.
Sort the dividing ball with three last balls unsorted yet.
After the 4th step we have a directed graph of 12 sorted balls. The ball that was dividing on the previous step is still the dividing ball.
Now we have to sort N balls that are heavier than the dividing ball and M balls that are lighter than it.
N = 4, M = 7 or M = 4, N = 7 - no problem, we can always do it in 1+4 = 5 steps, total step count is <= 9;
N = 5, M = 6 or M = 6, N = 5 - no problem, we can always do it in 2+3 = 5 steps, total step count is <= 9;
two other remaining cases are to be investigated
N = 3, M = 8 or N = 8, M = 3
N = 2 (sorted), M = 9 or N = 9, M = 2 (sorted)
other cases are impossible (N <=1, or N >= 10, or N/M = 2 and these two are unsorted are all prevented by the previous actions).
I think we can always sort 9 balls or 3 + 8 balls in 5 steps after the steps 1-4 because 9 or 8 balls are already split into sorted (or partially sorted) groups.
Sorting 2 remaining balls in a group of 3 can be done in the same step as sorting some 2 balls in a group of 8.
E.g., let's consider a case 9 = 3 + 3 + 2 + 1, balls in each group more than one ball (3, 3 and 2) are already sorted.
1) weigh the heaviest balls of each group, select the heaviest ball of 9;
2) weigh the lightest balls of each group, select the lightest ball of 9;
3) only 2 balls can be the second heaviest now and only 2 balls can be the second lightest.
Weigh these four balls, and we know the two heaviest balls and the two lightest balls of 9.
4-5) Sort remaining 5 balls. We did it in 5 steps, 5+4=9, it is OK.
I looked through all the cases and I saw that it can be done.
It would take a lot of time and space to write it there.
I'm not absolutely sure that I'm right and my calculations don't contain errors.
But I can bet some amount of money (e.g., 20 Euros) on my solution :-)
I also think that 8 steps are insufficient to sort 12 balls.
-----------------------------------------------------------------------