MATHEMATICAL ALGORITHM: MONOVARIANT

05 th March, 2019.

Mathematical algorithm can be expressed as a set of steps within a finite amount of time designed to accomplish some calculation, data processing and automated reasoning tasks. Algorithms can give us a deeper insight into mathematics. For instance, the well-known Euclidean algorithm essentially provides the foundation of number theory. Moreover, algorithms are effective tools in several services that impact our day-to-day lives. For example, the growing complexity of algorithms nowadays contribute to more advanced processors on smartphones or computers or the searching algorithms have improved the Google search applications which is very useful in optimizing traffic flow, etc.
Two of many extremely significant concepts in algorithms are invariants and mono-variants. A mono-variant is a quantity that changes monotonically, either non-increasingly or non-decreasingly, and an invariant is a quantity that remains unchanged. Let see the next example and how mono-variants play crucial role in constructing the algorithm.
In each regular hexagon’s vertices, we write randomly a nonnegative integer such that the sum of these numbers is 2019. We can perform to make moves of the following rule: pick one vertex and replace the number at this vertex by the absolute difference of two numbers at the neighboring vertices. Can we make a sequence of moves forcing all number in the hexagon’s vertices to 0.
Let a, b, c, d, e, f denote the number in 6 vertices in the order.

centered image

Figure 1. One illustration about the denotion.
Since sum of 6 numbers is 2019, we have two cases:
  • sum of three number in vertices 1,3,5 is odd, and sum of numbers in vertices 2,4,6 is even.
  • sum of three number in vertices 1,3,5 is even, and sum of numbers in vertices 2,4,6 is odd.
Without loss of generality, we assume sum of a, c, e is odd. We have two cases
  • Exactly one of a, c, e is odd. We assume that a is odd. Then we make the succesive moves at vertices 2, 6, 4, 1, 6. We end up with a situation that only one of 6 number is odd, which is number in vertices 2.

    • centered image

    Figure 2. The cycle after performing moves in the case a is odd.
  • Three number a, c, e are odd. We will make a sequence of moves at vertices 2, 4, 6, 3, 5. After that, we only get A is odd number.

    • centered image

    Figure 3. The cycle after performing moves in the case a, c, e are odd numbers.
This is the first sub algorithm: from any situation of the hexagon with odd sum, performing several moves can create the hexagon with exactly one odd number.
Now, our numbers include only one odd number assuming a. Note that the sum now is smaller than 2019. At this point, we realize that we can force all the number to 0 by reducing the sum or the maximum of them. It seem to be a lot of cases to consider when you want to choose the mono-variant is the sum of all numbers, but not for the case of choosing the mono-variant as the maximum. Note that the maximum is never increase.
Here is the second sub-algorithm: from a hexagon with exactly one odd number, make the hexagon such as the sum of all number in hexagon’s vertices Is odd and the maximum of these number is strictly smaller than the maximum of the initial hexagon or make all number in the hexagon’s vertices equal to 0.
If the maximum of hexagon now is even, then at least one of b, c, d, e, f. Then if we make moves at vertices 2, 3, 4, 5, 6 in the order, the maximum will be decrease, and still keep the properties of odd sum of all 6 numbers.
If the maximum is odd, then a is the maximum, we have two case:
  • if c=e =0 , we perform moves at vertices 2, 6, 4, 1, 2, 6, which makes all numbers equal to 0.
  • if at least one of c and e is not 0, suppose c is greater than 0, we perform a sequence of moves at vertices 2, 6, 1, 6. This moves decrease the maximum and still keep the odd sum property.
This sequences of moves is very natural and easy to create satisfying our intentions, but not pick randomly. Our advice is to play around with small cases several times, you can create your own sequence of moves. Beware of that there are a lot of different way to achieve our objective in both 2 sub-algorithms, therefore you might end up with the difference sequence of moves.
To sum up, the main algorithm can be defined as following
While all the number in hexagon is not 0 do
  • If the hexagon has not exactly one odd number.
    • Do the first sub algorithm;
    • End;
  • Do the second sub algorithm;
    • End.

It can be easy to see that the problem can be generalised by replacing 2019 by any odd numbers. How about other factors: can we replace the odd sum with even sum? Here is the counter example.

centered image

Figure 4. Counter example.
Reference:
1. Principles of Algorithmic Problem Solving, Johan Sannemo, October 24, 2018.
2. Algorithmic, Anany Levitin and Maria Levitin, 2011.



Comments Please: