Recall that the 
Suppose that you want to send a message so that it will reach all vertices of the discrete 
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 
Test your intuition: Is there a better strategy?
Here is a link to previous posts in the “Test-your-intuition” series.
Combinatorics and more 
Hi Gil,
Unless I’m misunderstanding, I think you shifted notation in here somewhere: at first I think you say the entries of the vector have to be $\pm 1$, but then later you mention a vector $(0,0,\ldots, 0)$. Of course the situation is equivalent if you equate $\{-1,1\}$ with $\{0,1\}$, but it might help your readers to edit that.
Best,
greg
GK: Dear Greg, thanks, corrected.
PS. Interesting problem
My intuition tells me you wouldn’t ask the question if there was known to be a better strategy.
My intuition tells me you wouldn’t ask the question unless there were known to be a better strategy.
Dear Tom and Rodney, “Second-order” intuitions for deducing the answer to a problem, like Tom’s intuition and Rodney’s intuition are actually quite interesting. (And they are quite relevant in theoretical economics, game theory, and psychology.) Such intuitions may depend on “framing effect” e.g. the precise wording of the question. For example, would you change your intuitive answer which is based on guessing my motivation had I asked the question:
Of course, if we want to sharpen our mathematical intuitions in order to solve open problems it is less clear how useful such “second-order intuitions” are.
My intuition tells me that if I pick message targets uniformly at random, then w.h.p. even after I’ve picked as many as n/2 of them I won’t have seeded the message at any point much closer than n/2 steps away from (0,0,0,…). So the random strategy still takes approximately n/2 steps just to cover (0,0,0,…) let alone the whole cube. It’s difficult to distribute codewords much more evenly than that, so I suspect n/2 – o(n) is the right answer. Of course that’s far from being a rigorous solution…
My first intuition actually tells me that the transmission feels like I could just regard it as a chain. Thus, I’d put the thing about 2/3 down the line and get roughly n/3.
David’s intuition looks completely correct: n/2 – o(n) rounds are necessary. (I suspect, however, that Gil wants us to think about what the right o(n) term should be…)
To get a slightly stronger result, let’s let our cost measure C(S) of a (possibly randomized) strategy S be the expected number of rounds to hit a uniformly chosen point in the hypercube; we’ll show that C(S) > n – o(n).
By convexity, C(S) is minimized by some deterministic S. WLOG, this S is oblivious, so let v1, v2, …, vi, … be its fixed choice-sequence, where vi is given the message at step i.
If x is chosen uniformly from the hypercube, then for each fixed i, dist(x, vi) is distributed as a sum of i Bernoulli trials with parameter 1/2.
So by Chernoff bounds (please check my statement), with probability greater than 1 – n^(-2), it’s within O(sqrt(log n)) standard deviations of its expectation (n/2); i.e., in this case
|dist(x, vi) – n/2| ( n/2 – O(sqrt(n log n) ) * (1 – O(n^(-1)) ) = n/2 – O(sqrt(n log n)).
Fixing typo: dist(x, vi) is distributed as a sum of n Bernoulli trials (not i trials) with parameter 1/2.
Sorry, the last line in my first comment was mangled by html, and the end of my argument was cut off.
Finishing up with last eqn corrected:
…i.e., in this case
|dist(x, vi) – n/2| is less than O(sqrt(n log n)).
So, by a union bound, with prob. > 1 – O(n^(-1)), we have
|dist(x, vi) – n/2| less than O(sqrt(n log n)) for i = 1, 2, …, n/2.
Thus, C(S) is greater than
(1 – O(n^(-1)))(n/2 – O(sqrt(n log n))) = n/2 – O(sqrt(n log n)).
Going deeper into the second-order discussion, I wonder why the question was not posed in the following *almost* equivalent form: can you cover the unit n-cube with less than
balls of (Hamming) radius less than 
?
Other than that, my only bit of wisdom is that the Hadamard code shows you certainly cannot do with less than
rounds. Remember that the Hadamard code consists of n+1 cube vertices with every pair at distance 
(geometrically, they are the vertices of a regular simplex inscribed in the cube). A Hadamard code is conjectured to exist whenever n+1 is a multiple of 4 and known to exist for infinitely many values of n (in particular, whenever n+1 is a power of two).
There are several ways to formulate the question but I think you want to cover by Hamming Balls
do that the radius of Ball i is r-i and r is as small ass possible.
Yes, my question is whether “r balls of radius less than r (and r is as small as possible)” would make a difference.
My favourite Turing Machine’s intuition tells me that if there is a better strategy, then N is at least 15. I think the V.A. also gives a lower bound of N/2-O(sqrt(N)).
GK: Am I guessing right that V. A. stands for “Volume argumets?”
That’s exactly what I meant — but I think I calculated too quickly and that the easy lower bound instead is like N/2-O(sqrt(N*log(N)))
If one could broadcast to all the vertices of a dominating set of an n-cube at once in the next round one would have the message to all vertices. So one approach would be to broadcast to the vertices of a dominating set one after another, and one time unit after reaching all of these one would be done. My guess is that minimum dominating sets will vary in a complex way with n.
Dear Joe, every vertex of the n-cube dominates n+1 vertices, so a dominating set cannot be smaller than
. This is much more then needed. The point is that when you send a message to a vertex v at round i then at round i+j the message will reach all vertices of Hamming distance 
j from v. Even if you send the message to a single vertex at the first round and stop it will reach all vertices after n+1 rounds.
Thanks. Joe
Did you ever post a follow-up to “Test Your Intuition (13)”? I solved the problem game-theoretically, but I don’t know the connection to the Barca-Inter match(es).
Dear Rex, not yet. thanks for reminding me…
I believe there is no faster way to cover all the nodes.
Take the case where the dimension, n, is a power of 2. Now
consider only those vectors with exactly n/2 1’s (and therefore also
n/2 0’s). These are the corners that are covered last by expansion of the origin. If you are to cover the cube any faster than n/2, you will have to cover these by your actions after step two. There is a subset of these that are all pairwise at least n/2 distant from each other (i’ll show the vectors for n=8 instead of defining them generally because its easier)
(11110000)
(00001111)
(11001100)
(00110011)
(11000011)
(00111100)
(10101010)
(01010101)
(10100101)
(01011010)
(10010110)
(01101001)
(10011001)
(01100110)
notice that there are 2n-2 of them. Therefore, there are too many of them, too far from each other to cover by hand any faster than n/2. Therefore there is no better strategy than to just dit and wait.
Dear Pat, impressive! GK: I realize that the argument is incomplete (see discussion below). A combinatorial proof of this kind that you cannot do better would be interesting even for special values of n
Isn’t there something else you need to argue? Let D be this set of 2n-2 points which are mutually (n/2)-distant. You could still cover more than one point from D “quickly” by picking a point which is “between” them. For example, 11001111 is at distance 2 from two of the points in your list. Can you preclude, for example, that there is a point X which is at distance n/3 from 3 points in D?
because hamming distance is a ‘taxicab’ metric, you cannot cover more than 2 of the points with any ball of diameter < n/2.
i meant radius, sorry.
*sit* and wait
just to clarify, the uncoverable corners have a nice recursive structure: the vectors for dim 2^n form the first and second halves of the vectors for dim 2^(n+1), and are matched with either another copy of themselves, or their negation. so for example, one of the corners for n=8 is:
(11001100)
so for n=16 we get two vectors:
(1100110011001100) and
(1100110000110011)
and so its easy to show there are 2n-2 of them, and that the necessary pairwise distance properties hold.
If you include the origin (00…00) and the far corner (11..11) in this set it actually all works out a bit more simply: there are then always a set of 2n distant corners and the asymmetry of having to pick the far corner for the second move is removed.
you can cover many of the points in your set by a ball of radius less than $n/2$. e.g. 11101000 is at distance 2 from three of the points in your example for $n=8$.
yes you are correct (and i was wrong in my comment to daveagp above)
@myself
Well, the binary [24,12,3] Golay code is perfect, thus the radius 3 Hamming spheres around its
2^12 codewords don’t overlap. Even in this case, you’ll take 2^12 time steps to send the message to each of the codewords and an extra 2 steps will be required for the last codeword’s 3-sphere to be filled. Thus, this code allows you to use 2+2^12 steps which is of course no joy.
Of course I neglected to say that the 3-spheres cover the whole space of 24-bit strings.
My intuition also said that you couldn’t do better. Here’s why. Suppose you strengthen what you’re allowed to do as follows. At the very first go you may place t points and their antipodal points. Then you just sit back and wait. After
further steps, the points not reached from x and its antipode form the intersection of the cube with a hyperplane, and this intersection is pretty big. The points not reached at all form an intersection of t hyperplanes of this kind. Here’s where my intuition starts to desert me. In 
I could argue that even if 
there will be a point in the intersection (of a 1-dimensional subspace with the sphere). But if we’re restricting to the discrete cube, it’s not clear that this dimension argument remains valid. On the other hand, t is quite a bit smaller than n. But perhaps this is the whole issue. (I don’t rule out that my numbers are out by approximately 1, by the way.)
My initial intuition thought no, but now I think maybe. I’ve just been on holiday, which gets me going. And I got thinking about a tetrahedron inscribed in a cube. So with 12 co-ordinates choosing successively (0,0,0,0,0,0,0,0,0,0,0,0); (1,1,1,1,1,1,1,1,0,0,0,0); (1,1,1,1,0,0,0,0,1,1,1,1); (0,0,0,0,1,1,1,1,1,1,1,1) i.e. choosing strategic points 2/3 of the way across [rather than the whole way across] – now with this few co-ordinates you don’t beat the original, but I think you can with n=24.
Having thought about it more, I’m not at all sure that any such thing will work …