Números com dígitos distintos
On Janeiro 11, 2021 by adminConsidere o conjunto de números naturais de 0 a 999, inclusive. Suponha que selecionemos algum subconjunto desse conjunto de forma que qualquer par de números dele compartilhe não mais do que um dígito nas mesmas posições. Para esclarecer,
- pares como 123 e 456 são obviamente permitidos, uma vez que não compartilham nenhum dígito em comum.
- 123 e 321 são permitidos juntos desde, enquanto eles têm os mesmos dígitos exatos, apenas o 2 está realmente na mesma posição.
- 812 e 212 não seriam permitidos, pois ambos compartilham o “12” em seu final, que tem dois dígitos.
- 206 e 246 não são permitidos da mesma forma; os dígitos compartilhados não precisam ser contíguos.
- Zeros à esquerda são importantes, então 5 e 205 são um par proibido como Nós vamos. (Pense em 5 como “005”.)
Lembre-se de que isso deve valer para cada par de números no subconjunto. Qual é o maior (como em a maioria dos elementos ) conjunto possível que satisfaz esta condição? Que tal o conjunto com a maior soma dos elementos?
(Quebra-cabeça inspirado em uma conversa com um amigo a respeito da digitação incorreta de números de ID. Pedimos desculpas se isso já foi perguntado aqui.)
Resposta
Para saber o que vale, Eu tenho uma visualização clara de por que a resposta é 100:
Primeiro imagine um caso mais fácil, onde você tem todos os números 0-99 e não pode ter dois números compartilhando qualquer dígito no mesmo lugar; podemos desenhar uma tabela de números como esta:
Observe que cada número em uma linha compartilha seu primeiro dígito, e cada número em uma coluna compartilha seu segundo dígito. Portanto, você deve escolher números de forma que dois não compartilhem uma linha ou coluna. É bastante claro que a quantidade máxima de números que você poderá escolher é 10. Esta é uma solução:
Agora, considere o caso colocado na pergunta. Obtenha 10 dessas tabelas 0..99, exceto a segunda tabela tem 100..199, a terceira 200..299 e assim por diante. Em seguida, coloque-as uma atrás da outra para formar um Grade 10x10x10 de 0..999 (inseri alguns dos números para ter uma ideia):
Observe que todos os números em qualquer “faixa” de dez cubos (linha ou coluna) compartilham 2 dígitos em comum. Portanto, você precisa escolher números de forma que nenhum número compartilhe uma “faixa”.
Depois de pensar um pouco, está claro que você só conseguirá para escolher 100 desses números.
Resposta
Para adicionar à resposta PrisonMonkeys “, cada conjunto com 100 elementos terão a mesma soma, que é 49950. Para cada local no número, cada dígito só pode aparecer naquele local e no máximo 10 vezes, pois não pode aparecer duas vezes com o mesmo valor para outro local. Isso significa que cada dígito deve aparecer em cada local exatamente 10 vezes, para que haja um total de 100 números no conjunto. Portanto, podemos somar cada posição separadamente para obter 45000 + 4500 + 450 = 49950.
Resposta
Tenho uma solução com 100 elementos do conjunto. Gere cada número da seguinte maneira:
Para o elemento $ 0 \ leq n \ leq 99 $, adicione
ABC
a o conjunto ondeAB
é $ n $ (com um zero à esquerda se $ n < 10 $) eC
éA+B mod 10
. Portanto, para $ n = 3 $,AB
é03
eC
é0+3 mod 10=3
, o que significa queABC
é033
.
Não há pares de números neste conjunto que violem a condição (que eu saiba). E não há um número de três dígitos ABC
com uma parte AB
diferente, já que cobri todas as 100 possibilidades. O que significa que este é o maior conjunto possível que satisfaz a condição.
Não tenho solução para a segunda questão ainda.
Comentários
- sua explicação do conjunto parecia um tanto obscura. Tentei limpar para tornar mais fácil de entender. Sinta-se à vontade para alterá-lo se achar que eu não ' não capturei o que você estava tentando dizer.
- @RobWatts Obrigado, isso é exatamente o que eu era tentando dizer. Parece mais fácil de entender, embora ' seja meio difícil de dizer, eu já entendi o que quis dizer.
- Olá. Você pode adicionar um exemplo com n > 10, por favor?
- @Kalissar Por exemplo $ n = 57 $, então
AB
é57
(A=5
eB=7
), eC
é5+7 mod 10=2
, entãoABC
é572
.
Deixe uma resposta