>>12532257Intuitively it's obvious to any non-midwit that this is impossible for any number of cubes.
To prove it formally, I introduce the position function that returns cube at position . In the initial state for all cubes (cubes are in correct positions). Cube positions can only be modified via the swap function that takes two positions and , and we count the number of times that function is called.
Now we need one helper metric for the proof, specifically the cycle length of a position. Let a cycle be defined as a series of positions such that , where is the cycle length. The function returns the length of the cycle that x is a part of. Trivially, all cycles are of length 1 in the starting position. We also note that where R is a set containing exactly one representative element of each cycle.
Any call of has the following effects on cycles: If and are not in the same cycle, their cycles are combined. This means that , where denotes position x after the swap. What's important to note, is that sum of cycle lengths-1 increments by 1 after such an operation: , since , but there is one less cycle in the sum to decrement 1 from.
In the same way, the opposite happens if and are already in the same cycle. In that case their cycle is broken into two cycles, and the sum of cycle lengths-1 is reduced by one: .
1/2, also hope I didn't fuck up formatting
