Hamming distance
It is clear that either the Hamming distance between "M1" and "s"’ is at most "d"’ or the Hamming distance between "M2" and "s"’’ is at most "d"’. Either "M"1 or "M"2 occurs in every input string at a Hamming distance of at most "d"’. As a result, in at least "n"’ strings (where "n"’ = "n"/2) either "M"1 or "M"2 occurs with a Hamming distance of at most "d".