Podemos comparar dos números secretos?

Question

Si usted y yo cada uno tiene un número secreto, hay una manera en que podemos averiguar de quién es más grande sin la revelación de nuestro número secreto?

Claramente un tercero de confianza podría hacer el trabajo, pero me preguntaba si hay algún matemático o de cifrado truco que podría ser utilizado.

Para ejemplos prácticos, considere la posibilidad de dos personas que se quieren comparar el salario, o la edad, o el número de entradas de exceso de velocidad, etc.

Answer 1

Sí, este es Yao Millonarios del Problema!

Answer 2

No matemáticamente riguroso, pero tal vez lo más práctico:

Supongamos que se puede reducir el número a uno de los diez valores. Tal vez usted está dispuesto a ronda de sus salarios a la más cercana de 5K y piensas que están entre 50K y 95K, o ambos estuvieran dispuestos a anunciar que tenía menos de 10 entradas de exceso de velocidad.

Cada uno de ustedes debe tomar la mitad de una baraja de cartas. Elegir una tarjeta marcador (tal vez un As - algo fácil de recordar) y mostrar a la otra persona. Ahora, como usted junto contar a través de los posibles valores, que se turnan para colocar una tarjeta boca abajo en una pila común. Al llegar a su número, se pone el marcador de la tarjeta hacia abajo. Cuando haya terminado de contar, tiene 20 cartas en la pila y sea cual sea el marcador de tarjeta está en la parte superior indica que la persona que tiene el número más alto, pero no se puede mirar todavía!

Por ejemplo, si la primera persona que tiene 2 entradas de exceso de velocidad (marcador de tarjeta verde), y en el segundo, 4 (marcador de tarjeta en rojo), la pila crecería como este:

Ahora que cada uno toma su turno la celebración de la pila por debajo de la mesa mientras se pone una de sus cartas restantes en la parte superior de la pila y algunos por debajo de la pila. Después de cada hecho esto, usted no sabe la profundidad de la cubierta original de la pila de 20 tarjetas. Pero en algún lugar, y el marcador superior de la tarjeta indica todavía cuyo número es mayor.

Para el ejemplo anterior, la cubierta ahora tendría que ser algo como esto:

A continuación, puede voltear las cartas de la parte superior de la pila hasta llegar a una de sus tarjetas de marcación. Si es el marcador de la persona que fue a poner su tarjeta de segundo en cada número de anuncio, usted debe verificar la siguiente carta también, a ver si tenemos un empate. Inmediatamente baraja el mazo.