[35] Given an n-dimensional cube and a permutation of its nodes, each node v wants to send an information packet to node (v) as

[35] Given an n-dimensional cube and a permutation π of its nodes, each node v wants to send an information packet to node π(v) as fast as possible. Label every edge in the cube with its dimension from

{1,...,n}. A route (v1 → v2 → ··· → vk) is ascending if (vi, vi+1) has higher dimension than (vi−1, vi) for all 2

Step 1. For every node v, choose randomly a node w. Node v sends its packet over the uniquely determined ascending route to w.

Step 2. Send the packet from w to π(v) through the unique ascending route. Prove that for every constant

c, algorithm Aπ finishes with probability greater than 1 − 2−(c−5n−O(1))/2 after at most 2n + 2c steps.
Comments. Hint: Show that the description of a route on which too many collisions occur can be compressed. Source: [L.G. Valiant and G.
Brebner, Proc. 13th ACM Symp. Theory Comput., 1981, pp. 263–277;
S. Reisch and G. Schnitger give an incompressibility proof in Proc. 23rd IEEE Found. Comput. Sci., 1982, pp. 45–52].