Caras, não esperem nenhuma beleza matemática notável ou algoritmos úteis na vida. Estou escrevendo por puro interesse esportivo. Fiquei interessado no problema publicado aqui , com o qual prisioneiros americanos desfazem suas enormes sentenças. A julgar pelos comentários ao artigo, ele já despertou algum interesse na comunidade. Eu entendo que não estou indo muito bem, deveria ter dado às pessoas tempo para pensar por si mesmas. Porém, eu me arrependo, sou um pecador, não posso resistir. E eu posto minha decisão aqui. Quem se importa, bem-vindo ao gato. Se você quiser pensar um pouco mais por conta própria, não leia ainda.
Portanto, a tarefa em si. Vou formulá-lo um pouco mais claramente do que no próprio artigo (ai, a tradução aí está um pouco torta).
O dial (como na Figura 1) pode apontar para qualquer número inteiro de 1 a n quando girado no sentido anti-horário. A contagem regressiva começa em 1, então a seta gira sequencialmente (sempre no sentido anti-horário) uma posição, depois duas, depois três e assim por diante, até a última volta na posição n-1. Coletamos a sequência de todos os números apontados pela seta.
Por exemplo, se n = 12, você obtém a sequência 1, 2, 4, 7, 11, 4, 10, 5, 1, 10, 8, 7. Pode-se ver que há números repetidos nela.
E para n = 8, a sequência será 1, 2, 4, 7, 3, 8, 6, 5. E não há números repetidos nela.
A questão é: para quais valores de n os números na sequência não se repetem?
Apresentado por Gary Gordon e Denise Ozbay, novembro de 2020, Mathematical Horizons.
Vamos chamar a sequência, que é construída no problema, de sequência do n-dial . E números, n para os quais esta sequência não contém números repetidos, são adequados .
Vamos começar recebendo uma dica muito séria. Resposta quase imediatamente pronta. Não fui para as prisões americanas e não sei se há computadores disponíveis para os presos de lá. Mas eu tenho meu cavalo de guerra na minha mesa! Portanto, é um pecado não usá-lo. Lançamos nosso Jupyter Notebook favorito e entramos em um pequeno programa:
def getSeq(n): # n-
lst=[]
s=1 #
d=1 #
for i in range(0, n):
lst.append(s)
s=(s+d) % n
if s==0:
s=n
d=d+1 # 1
return lst
def testSeq(lst): #
if len(set(lst)) == len(lst):
return True
return False
def getList(n): # , 2 n
lst=[]
for i in range(2, n):
if testSeq(getSeq(i)):
lst.append(i)
return lst
Executar getList (12345) fornece uma lista de 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192.
Portanto, parece muito provável que apenas potências de dois sejam números válidos, e nada mais. Resta provar isso. Mais precisamente, duas afirmações terão que ser provadas:
1) Qualquer potência de dois é um número adequado.
2) Qualquer número que não seja uma potência de dois não é adequado.
Primeiro, vamos ver de onde vêm os números repetidos na sequência de n-dial.
A sequência começa em 1. Seu incremento na primeira etapa também é igual a 1 e, a seguir, a cada etapa aumenta em 1. O restante da divisão por n é considerado o resultado. Além disso, se o resto for zero, o resultado é considerado igual a n. Vamos tentar construir essa sequência para algum número n não muito grande. Por exemplo, n = 6:
s (1) = 1 (mod 6) = 1
s (2) = 1 + 1 (mod 6) = 2
s (3) = 2 + 2 (mod 6) = 4
s (4) = 4 + 3 (mod 6) = 7 (mod 6) = 1
s (5) = 7 + 4 (mod 6) = 11 (mod 6) = 1 + 4 (mod 6) = 5
s (6) = 11 + 5 (mod 6) = 16 (mod 6) = 5 + 5 (mod 6) = 4
Vemos que dois pares coincidiram: s (1) es (4), es (3) e s (6). Além disso, se tomarmos os valores não módulo, a diferença entre os elementos maiores e menores de ambos os pares é um múltiplo de 6. Isso, em geral, é bastante compreensível. O valor final é obtido módulo n. E se, antes de tomar o módulo, os números diferirem por n (ou um múltiplo de n), então os valores finais coincidirão.
Por outro lado, uma vez que o incremento que temos em cada passo aumenta em 1. E é claro que as diferenças acima são iguais às somas de alguns números consecutivos. Por exemplo, para o par s (1), s (4):
7 = 1 + (1 + 2 + 3)
E para o par s (3), s (6):
16 = 4 + (3 + 4 + 5)
Para o primeiro a diferença é 6 para o par e 12 para o segundo.
Assim, chegamos a uma conclusão importante:
Se números coincidentes aparecem na sequência do n-dial, então n ou seu múltiplo pode ser representado como a soma de alguns números consecutivos, o maior dos quais não excede o número n-1.
Primeiro, provamos uma afirmação auxiliar:
qualquer número que não seja uma potência de dois pode ser representado como uma soma de números consecutivos. Nenhuma potência de dois pode ser representada pela soma de números consecutivos.
Vamos pensar em como representar geralmente algum número como uma soma de números consecutivos. Para os estranhos, isso é bastante simples. Se A for ímpar, pode ser representado por um par:
A = [A / 2] + ([A / 2] + 1), onde [] significa a parte inteira do número.
Por exemplo, 11 = [11/2] + ([11/2] + 1) = 5 + (5 + 1) = 5 + 6.
É apenas isso para múltiplos de 3. Se A for um múltiplo de 3, então:
A = (A / 3 - 1) + A / 3 + (A / 3 + 1).
Da mesma forma, se A for um múltiplo de 5:
A = (A / 5 - 2) + (A / 5 - 1) + A / 5 + (A / 5 + 1) + (A / 5 + 2).
E, em geral, se o número A tiver um divisor ímpar B, ele pode ser representado como uma soma de B números consecutivos, e o número A / B está exatamente no meio.
Exemplos:
27 = 3 * 9. Portanto, 27 = (9-1) + 9 + (9 + 1) = 8 + 9 + 10,50
= 5 * 10. Portanto, 50 = (10-2) + (10-1) +10 + (10 + 1) + (10 + 2) = 8 + 9 + 10 + 11 + 12.
O oposto também é óbvio. Se um número for representável como a soma de um número ímpar de números consecutivos, ele terá um divisor ímpar e a própria representação terá a forma descrita acima. Portanto, a potência de dois não pode ser a soma de um número ímpar de números consecutivos , porque não possui divisores ímpares.
Mas e quanto à soma de um número par de números consecutivos? A soma de dois números consecutivos é sempre ímpar. Esperançosamente, isso é óbvio. A soma de quatro pode ser considerada a soma de dois pares, cada um dos quais ímpar. Portanto, a soma de quatro é par. A soma de seis é novamente ímpar, a soma de oito é par e assim por diante. Aqueles. a soma de um número par de números consecutivos é igual se o número for um múltiplo de 4 e ímpar se for um múltiplo de apenas 2.
Seja um número par A a soma de 4 * k números consecutivos. Para simplificar, seja k = 1, para k grande o raciocínio é completamente análogo:
A = a + (a + 1) + (a + 2) + (a + 3) = 4 * a + 6.
Divida essa igualdade por 2 :
A / 2 = (4 * a + 6) / 2 = 2 * a + 3 = (a + 1) + (a + 2).
Aqueles. novamente obtemos a soma dos números consecutivos.
Portanto, se para um número par A houver uma representação na forma da soma de um número par de números consecutivos, então alguma representação na forma de uma soma de números consecutivos existe para A / 2 .
Por exemplo:
26 = 5 + 6 + 7 + 8. Portanto, 26/2 = 13 = (5 + 1) + (5 + 2) = 6 + 7.
Suponha que para a enésima potência de dois haja uma representação na forma de uma soma de um número par de números consecutivos (não há representação na forma de um número ímpar para ele, como mostrado acima). Então, há uma representação na forma de uma soma de números consecutivos para o grau N-1. E o número de termos nele também é par. Por indução, o mesmo pode ser dito sobre o grau N-2 e sobre o grau N-3 e, em geral, sobre qualquer grau menor que N. Mas não há representação na forma de uma soma de números consecutivos para o número 4, que é fácil de ver. Portanto, nenhuma potência de dois pode ser representada como uma soma de números consecutivos .
Por outro lado, qualquer número que não seja uma potência de dois pode ser representado como uma soma de números consecutivos. Se esse número for ímpar, ele pode ser representado como um par. Se for par e não uma potência de dois, então terá pelo menos um divisor ímpar. E representável por meio dele.
A declaração auxiliar está comprovada.
Considere toda a seqüência n-dial.
s (1) = 1 (mod n)
s (2) = 1 + 1 (mod n)
s (3) = 2 + 2 (mod n)
s (4) = 4 + 3 (mod n)
...
s (n ) = s (n-1) + n-1 (mod n)
Seja n uma potência de dois. Então 2 * n, 4 * n, 8 * n, etc., também são potências de dois. E como soma de números consecutivos, eles não são representáveis. Representáveis são 3 * n, 5 * n, 6 * n, 7 * n, 9 * n, etc. Aqueles. o número m * n deve ter pelo menos um divisor ímpar. No entanto, mesmo o menor desses múltiplos, 3 * n, deve ser representado como
(n - 1) + n + (n + 1).
Não há outras representações do número 3 * n. Pois n como uma potência de dois não tem nenhuma representação (consulte a instrução auxiliar). Mas os termos nesta soma não devem exceder o número n - 1. Portanto, 3 * n como uma diferença nunca aparecerá. Para outros múltiplos, o raciocínio é exatamente o mesmo. É claro que nem n nem 2 * n aparecerão como diferenças, como potências de dois. Portanto, qualquer potência de dois é um número adequado.
A afirmação (1) está comprovada.
Agora, não deixe n ser uma potência de dois. Aqueles. representável como uma soma de números consecutivos. A diferença entre o primeiro e o último membro da sequência (antes de tomar o módulo por n) será:
d = 1 + 2 + 3 +… + (n-1).
E as diferenças entre os membros da sequência n-dial (antes de fazer o módulo) serão quaisquer somas parciais desta série. Se n for representável como uma soma de números consecutivos, então os maiores números possíveis que compõem essa soma são
[n / 2] e [n / 2] + 1. ([] é a parte inteira de um número)
Todos os outros as variantes de tal soma são compostas de números ainda menores ... Isso significa que os membros da seqüência do dial n, com uma diferença antes de tomar o módulo igual an, certamente serão encontrados. E depois de pegar o módulo, eles darão os números correspondentes. Aqueles. qualquer n que não seja uma potência de dois e, portanto, representável como uma soma de números consecutivos, não é um número adequado.
A declaração (2) está provada.
No total, a tarefa está completamente resolvida. Números adequados são quaisquer potências de dois e não outros. À liberdade com a consciência limpa !!!
A moral desta fábula é talvez apenas uma. Gente, mesmo que você faça matemática pura, não negligencie os experimentos computacionais. Sim, esses experimentos não provam nada. No entanto, eles podem dar um palpite bem fundamentado. Embora possa não ser tão simples como aqui. E provar geralmente é muito mais fácil do que adivinhar. Eu ficaria feliz se alguém achasse esta apresentação útil e interessante.