Recall that the -dimensional discrete cube is the set of all binary vectors ( vectors) of length n. We say that two binary vectors are adjacent if they differ in precisely one coordinate. (In other words, their *Hamming distance* is 1.) This gives the -dimensional discrete cube a structure of a graph, so from now on , we will refer to binary vectors as vertices.

Suppose that you want to send a message so that it will reach all vertices of the discrete -dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the message at round all its neighbors will receive it at round .

The question is

how many rounds it will take to transmit the message to all vertices?

Here is a very simple way to go about it: At round 1 you send the message to vertex (0,0,0,…,0). At round 2 you send the message to vertex (1,1,…,1). Then you wait and sit. With this strategy it will take rounds.

Test your intuition: Is there a better strategy?

Here is a link to previous posts in the “**Test-your-intuition**” series.