Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / B / 8 / a / Solution

On this product, use the Hamming metric $d(x,y)=|\{i:x_i\ne y_i\}|$. The relevant Lipschitz condition is $|f(x)-f(y)|\le d(x,y)$, equivalently changing any one coordinate changes the function by at most one. More generally an $L$-Lipschitz function has bound $Ld(x,y)$. The unit version is the bounded-differences condition used below.