0

Say that $S$ contains binary strings of length $n$ s.t. no two strings in $S$ differ in exactly one position.

How would I prove that $S$ contains no more than $2^{n-1}$ strings (Note $n$ can be any positive integer)

I can't seem to find a way to do even start this problem.

Kenta S
  • 16,151
  • 15
  • 26
  • 53
Jhin
  • 45

2 Answers2

0

Let $S$ be as described. Since each word of $S$ differs by at least two letters, we can create a new set $S'$ where each word of $S'$ is exactly the same as a word from $S$, except with any single letter removed. Then each word in $S'$ is still distinct from every other word in $S'$, and each word in $S'$ now has length $n-1$. Therefore, there are at most $2^{n-1}$ words in $S'$.

But since there is a one-to-one correspondence between this set $S'$ and the original set $S$, we see that $S$ has at most $2^{n-1}$ words in it.

Kyle
  • 544
  • Not sure if i'm misinterpreting the question but say for example n = 2. Then we will have 2^2 = 4 binary strings ie. {00, 01, 10, 11}. To fit the statement of S the set has to be {00,11} which is less then 2^(2-1) = 2. So from your example S' = {0,1} correct? – Jhin Oct 10 '19 at 03:58
  • In your example {00,01,10,11} you don’t fit the requirements of the set. Namely, 00 and 01 differ by a single letter. Also, 00 and 10 do. So do (11 and 10) and (11 and 01). They must not differ in exactly 1 position to be eligible for your initial set. – Kyle Oct 11 '19 at 14:33
0

Let $A$ be the set of strings whose first bit is zero, and likewise $B$ for one. No element in $A$ can have all of its remaining bits match those of an element in $B$ (or else they would differ only by the first bit). Therefore, if you dropped the first bit of all elements in $S$, the strings would remain distinct. But there are only $2^{n-1}$ possible $(n-1)$-bit strings.

A_P
  • 1,007
  • I’m sorry I’m having trouble understanding how the first part of it answer about sets A and B implies the last statement in your answer. – Jhin Oct 10 '19 at 16:23
  • No two elements of A can share their final bits (because elements of a set must be distinct). The same is true of B. But also, no string in A can share final bits with any string in B. Therefore, the final bits of ALL the strings (in A and B combined -- in other words, in S) must be distinct. There are $n-1$ final bits. – A_P Oct 10 '19 at 17:04