Principio del palomar: ¿cuántos de tres dígitos de cadenas de bits debemos elegir para asegurarse de que dos de ellos están de acuerdo en al menos un dígito?

Question

Libros de texto de respuesta: 4

No veo cómo la respuesta es de 4, aunque. Porque elegir cualquiera de las dos cadenas de bits, decir 000 y 111 o 010 y 101, ¿no cualquier otra cadena de bits de acuerdo en una cifra de dos de esas cadenas de bits que no están de acuerdo en ninguno de los dígitos? Así que no, la respuesta será de 3? O me estoy perdiendo un caso especial?

Answer 1

Estás en lo correcto. Si usted escoge una cadena de bits, decir $b_1b_2b_3$, entonces si la segunda cadena de bits no están de acuerdo en cualquier dígito con la primera cadena de bits, entonces debe de ser $(1-b_1)(1-b_2)(1-b_3)$, es decir, el complemento bit a bit. Pero, a continuación, la tercera cadena de bits deben estar de acuerdo en algún lugar con uno de estos. (De hecho, se debe estar de acuerdo con al menos uno de estos en al menos dos lugares).

Como sus ejemplos indican, si la primera cadena de bits, por ejemplo, 011, a continuación, en orden a no estar de acuerdo en cualquier lugar, la segunda cadena de bits debe ser de 100, pero entonces no importa lo que el primer dígito de la tercera cadena de bits es, tiene que ser 1 o 0, en cuyo caso está de acuerdo con al menos una de estas cadenas.