PuzzleUp 2019

[uvo]

Meines Erachtens funktioniert deine 10, damit ist 11 nicht die Lösung.

Aber wlog/oBdA greift hier trotzdem nicht, weil du in dem nicht genannten Fall weniger Informationen hast. Nachdem du für den genannten Fall den weiteren Lösungsweg angegeben hast, muss noch explizit geprüft werden, ob dieser mit dem niedrigeren Informationsstand immer noch funktioniert - das tut er natürlich, aber allein die Notwendigkeit einer solchen Prüfung stellt ein Problem dar.

Mit wlog/oBdA kannst du Situationen wie
12&AB - 3 - 45&CD - 6 - 78
vs
12&AB - 3 - 45 - 6 - 78&CD
abdecken, weil du in diesen Fällen exakt die gleiche Menge an Informationen hast und damit ein analoger Lösungsweg automatisch funktioniert.

[Dandelo]

Ja, schon klar. Aber sie haben mich nach einer detaillierten Lösung gefragt, das habe ich ihnen geschickt. Und sie haben trotzdem 11 als beste Lösung drin.

Vielleicht heißt das ja auch, dass man die Bälle, die man zurück bekommt, doch nicht unterscheiden kann. Dann habe ich einen Algorithmus, der 12 Wägungen braucht. Das könnte dann auch mit 11 besser gehen.

Und SquareSums ist echt bitter. Mit Primzahlen kommt 47 raus, knapp daneben...

[Dandelo]

So ist es korrekt:

12&A - 3 - 45&B - 6 - 78&CD
12&AB - 3 - 45&CD - 6 - 78
12&ABC - 3 - 45&D - 6 - 78
12&ABCD - 3 - 45 - 6 - 78

1 to 8 in correct order

The groups (new groups, split by '-') in correct order, inside the groups the order is known for 1-8.

Benötigt wird innerhalb der Gruppen nur im dritten Fall, dass 1 leichter als 2 ist.

[dm_litv]

"Twelve Balls":

I have full (computer generated) solution tree for 9 (not 10) weighings.
Unfortunately, it seems impossible to give a human-readable explanation of the solution method.

[Dandelo]

I believe that, since my 10 weighings don't look optimal. I just tried to find a simple but reasonable algorithm. First I had 11, and when they asked me for a detailed solution, I couldn't reconstruct it, but found a better one.

BTW, I had no idea how to start a program, since brute force seemed impossible. Did you start with some intelligent heuristics?

[dm_litv]

Did you start with some intelligent heuristics?

I.
We assumed that the first 3 weighings are (1..4),(5..8),(9..12)

II.
Then we look at the task as at a two-person game.
Evaluation function Eval() of position - the number of possible ball permutations,
that do not contradict the results of already performed weighings.
The player A chooses move (4-ball subset), trying to minimize Eval()
on all possible moves (weighing results) of the player B.
Then we apply standard minimax search with alpha-beta pruning.

III.
Use the limitations of information theory.
 K**NMoves >= Eval()
where
 K - maximal number of outcomes during one weighing,
 NMoves - required number of moves.

A very important consideration that did not immediately come to my mind!
For first 3 weighings (from section I.)
 K = 24
After first 3 weighings
 K <=12
(because from four balls at least two belong to the same group).

If anyone is interested, here is a link to the file with the solution tree.
https://drive.google.com/open?id=1thtexe...P88NE3ezSu

[dm_litv]

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.

-----------------------------------------------------------------------

[Dandelo]

So they've changed it to 10....

It's my answer, but I don't believe it is correct.