Números con dígitos distintos
On enero 11, 2021 by adminConsidere el conjunto de números naturales del 0 al 999, inclusive. Supongamos que seleccionamos algún subconjunto de este conjunto de modo que cualquier par de números de él no comparta más de un dígito en las mismas posiciones. Para aclarar,
- Los pares como 123 y 456 obviamente están permitidos ya que no comparten ningún dígito en común.
- 123 y 321 están permitidos juntos ya que, mientras tienen exactamente los mismos dígitos, solo el 2 está realmente en la misma posición.
- 812 y 212 no estarían permitidos ya que ambos comparten el «12» al final, que es de dos dígitos.
- 206 y 246 tampoco están permitidos; los dígitos compartidos no necesitan ser contiguos.
- Los ceros iniciales son importantes, por lo que 5 y 205 son un par prohibido ya que bien. (Piense en 5 como «005».)
Recuerde que esto debe ser válido para cada par de números del subconjunto. ¿Cuál es el conjunto más grande (como en la mayoría de los elementos ) que satisface esta condición? ¿Qué tal el conjunto con la suma más grande de elementos?
(Rompecabezas inspirado en una conversación con un amigo por escribir mal los números de identificación. Disculpe si ya se ha preguntado aquí.)
Responder
Por lo que vale, Tengo una clara visualización de por qué la respuesta es 100:
Primero imagina un caso más fácil, donde tienes todos los números del 0 al 99 y no puedes tener dos números que compartan un dígito en el mismo lugar; podemos dibujar una tabla de números como esta:
Tenga en cuenta que cada número en una fila comparte su primer dígito, y cada número en una columna comparte su segundo dígito. Por lo tanto, debe elegir números de manera que no haya dos que compartan una fila o columna. Está bastante claro que la cantidad máxima de números que podrá elegir es 10. Aquí tiene una solución:
Ahora considere el caso planteado en la pregunta. Obtenga 10 de estas tablas 0..99, excepto que la segunda tabla tiene 100..199, la tercera 200..299, y así sucesivamente. Luego, superpóngalas una detrás de la otra para formar un Cuadrícula de 10x10x10 de 0..999 (he ingresado algunos de los números para darte una idea):
Ten en cuenta que todos los números en cualquier «franja» de diez cubos (fila o columna) comparte 2 dígitos en común. Por lo tanto, debe elegir números de manera que ningún número comparta una «tira».
Después de pensar un poco, está claro que solo podrá para elegir 100 de esos números.
Respuesta
Para agregar a la respuesta de PrisonMonkeys, cada conjunto con 100 elementos tendrán la misma suma, que es 49950. Para cada lugar en el número, cada dígito solo puede aparecer en ese lugar e como máximo 10 veces, porque no puede aparecer con el mismo valor para otro lugar dos veces. Esto significa que cada dígito debe aparecer en cada lugar exactamente 10 veces, para que haya un total de 100 números en el conjunto. Por lo tanto, podemos sumar cada lugar por separado para obtener 45000 + 4500 + 450 = 49950.
Respuesta
Tengo una solución con 100 elementos en el conjunto. Genere cada número de la siguiente manera:
Para el elemento $ 0 \ leq n \ leq 99 $, agregue
ABC
a el conjunto dondeAB
es $ n $ (con un cero a la izquierda si $ n < 10 $) yC
esA+B mod 10
. Entonces, para $ n = 3 $,AB
es03
yC
es0+3 mod 10=3
, que significa queABC
es033
.
No hay pares de números en este conjunto que violen la condición (que yo sepa). Y no hay un número de tres dígitos ABC
con una parte AB
diferente, ya que cubrí las 100 posibilidades. Lo que significa que este es el conjunto más grande posible que cumple la condición.
Todavía no tengo una solución para la segunda pregunta.
AB
es57
(A=5
yB=7
), yC
es5+7 mod 10=2
, entoncesABC
es572
.