6
$\begingroup$

This puzzle is related to this math question.

Consider $4$ lists of integers: $(0,0,0,0,0,0,0,0)$, $(1,1,1,1,1,1,1,1)$, $(2,2,2,2,2,2,2,2)$, $(2,2,2,2,2,2,2,2)$ where order does not matter.

We want to apply repeatedly some swaps, i.e. exchange an element of a list with an element of another list, till the absolute difference between the sums of the elements of any two lists is not greater than $2$.

I have counted $9$ swaps to get a possible valid configuration: $(0,0,0,1,2,2,2,2)$ (sum is $9$), $(0,1,1,1,2,2,2,2)$ (sum is $11$), $(0,0,1,1,2,2,2,2)$ (sum is $10$), $(0,0,1,1,2,2,2,2)$ (sum is $10$), with maximum difference $11-9=2$.

Is it possible to obtain any valid configuration in less than $9$ swaps?

$\endgroup$

1 Answer 1

12
$\begingroup$

We can easily show that the sums must be between 9 and 11. (If a sum was 8, the most the other 3 could be is 10 for a max sum of sums of 38. If a sum was 12, the least the other 3 could be is 10 for a min sum of sums of 42.)

At least one swap must involve a 1 because the list of all 1s needs to have a larger sum. Intuitively, swaps involving 1s are inefficient though as they change the sums by less.

So, we can swap a 1 and a 2 to fix the 1 list. Then we can swap five 2s into the 0 list -- two from the list we already swapped a 1 into and 3 from the other. This leaves us with sums 9, 10, 10, 11 in 6 total swaps. The lists are: $(0, 0, 0, 2, 2, 2, 2, 2)$; $(1, 1, 1, 1, 1, 1, 1, 2)$; $(0, 0, 1, 2, 2, 2, 2, 2)$; $(0, 0, 0, 2, 2, 2, 2, 2)$

It can't be done in fewer swaps because reducing each 2 list from sum of 16 to 11 or less requires at least 3 swaps (and swapping between them doesn't help).

$\endgroup$
2
  • $\begingroup$ The solution here feels too systematic for this page. Are these type of "puzzles" common here? $\endgroup$
    – Cruncher
    Dec 11, 2023 at 14:43
  • $\begingroup$ @Cruncher since anyone can answer any puzzle here, that includes more formal solutions too. While it's usually not a requirement, it's always nice to see some proof of optimality in many math-based puzzles. But for this specific puzzle, it has a tag "optimization", which mentions "There should ideally be a provable best answer, to avoid making the puzzle into an [open-ended] game" $\endgroup$
    – justhalf
    Dec 11, 2023 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.