Desafio 1949

Este é um desafio e tanto, para comemorar, hoje, 16/09/2019, os meus 10 anos de fórum :

Em 1949 um matemático indiano propôs, num congresso de matemática um desafio; passados 70 anos, ainda não foi provado. Refere-se aos números mágicos 6174 e 495

1) Escolha uma senha de 4 dígitos de 0 a 9 (pode começar por 0) ---> por exemplo 3214
2) Escreva os 4 dígitos em ordem decrescente: 4321
3) Escreva os 4 dígitos em ordem crescente: 1234
4) Subtraia o menor do maior: 4321 - 1234 = 3087
5) Repita os passos 2, 3, 4 ---> 8730 - 0378 = 8352
6) Repita os passos 2, 3, 4 ---> 8532 - 2358 = 6174

1) Escolha uma senha de 3 dígitos de 0 a 9 (pode começar por 0) ---> por exemplo 547
2) Escreva os 3 dígitos em ordem decrescente: 754
3) Escreva os 3 dígitos em ordem crescente: 457
4) Subtraia o menor do maior do maior:754 - 457 = 297
5) Repita os passos 2, 3, 4 ---> 972 - 279 = 693
6) Repita os passos 2, 3, 4 ---> 963 - 369 = 594
7) Repita os passos 2, 3, 4 ---> 954 - 459 = 495

Isto sempre acontece, variando apenas o número de passos até chegar nos números mágicos. 
Por exemplo se a senha for 050 basta apenas 1 passo: 500 - 005 = 495
As senhas escolhidas não podem ser números capicuas, com algarismos repetidos: por exemplo, 2222 e 777 não podem ser senhas.

Alguém se habilita a tentar provar???? Se conseguir, vai ficar famoso na comunidade matemática mundial!!!

Parabéns Mestre Elcioschin , obrigado por ajudar a mim e tantos outros estudantes nesses 10 anos de fórum, Deus te abençoe.

Muito interessante esses tais números mágicos.

Entre parênteses represento a soma dos dígitos:

5 = (5)
14 = (5)
26 = (
(26) = (35) = ...

Podemos ir encontrando os números cuja soma são iguais ao somar 0 ou 9:
5 + 9 = 14 = (5)
26 + 9 = 35 = (
(35) + 0 = (35)

Seja o número ABCD representável por 1000*A + 100*B + 10*C + D. Como os múltiplos de 10 não alteram o valor da soma dos algarismos, vamos desconsiderá-los. Ao subtrair o número espelhado, temos geralmente:

ABCD - DCBA = (A - D) + (B - C) + (C - B) + (D - A)

Obviamente a soma acima é 0, que tem o mesmo que 9 na soma dos algarismos.

6174 e 495 têm ambos peso 9.

Acho que não tem tanto a ver com a ordem, e sim com evitar algarismos repetidos (inclusive o algarismo simétrico).

Por exemplo, começando com 4321 - 3142 também chegamos em 6174: 1179->8532->6174.

Não estou dando uma resposta, mas algumas ideias.

Acho que é um bom começo!

Só notei uma falha, na frase:

"Ao subtrair o número espelhado, temos geralmente"

Numa demonstração este geralmente não pode ser aceito, teria que ser sempre

Realmente, seria necessário generalizar para uma demonstração.

Por outro lado, vou enfatizar que nos outros casos o resultado é o mesmo, as subtrações apenas não se agrupam da mesma forma tão naturalmente, por questões relacionadas ao "algoritmo" que usamos para subtrair números.

ABCD - DCBA = (A - D) + (B - C) + (C - B) + (D - A)

Por exemplo:
4321 = ABCD

ABCD - DCBA = 4321 - 1234

Na hora de realizar os cálculos, iremos tomar emprestado (ou somar 10 para o algarismo menos significativo e tirar 1 do mais significativo que ele, ou que não muda o resultado geral da soma dos algarismos, pois (10) = (1) na notação adotada):

... + (C - 1 - B) + (10 + D - A)

Está longe de ser uma demonstração, mas acho que podemos tirar algumas conclusões iniciais sobre o desafio.

É isto mesmo

4321 - 1234 = (4000 + 300 + 20 + 1) - (1000 + 200 + 30 + 4)

4321 - 1234 = 3000 + 100 - 10 - 3

4321 - 1234 = 3000 + _0 -+ (100 - 10) - 3

4321 - 1234 = 3000 + _0 -+ 90 - 3

4321 - 1234 = 3000 + _0 -+ 80 + (10 - 3)

4321 - 1234 = 3000 + _0 -+ 80 + 7

4321 - 1234 = 3087

Já fui por este caminho mas empaquei.
Não é à toa que o desafio está sem solução há 70 anos!

Elcio, estive pensando sobre esse desafio durante a semana. Sempre tive curiosidade e fui observador sobre a soma dos algarismos dos números.

Cheguei a alguns resultados que considero interessantes.

Uma primeira suposição era a de que não eram os números 6174 e 495 que eram especiais, mas os dígitos em questão. O interessante é que a soma final dos dígitos de ambos é sempre 9, que tem peso nulo na soma de dígitos. Por exemplo, 2 + 9 --> 11 --> 2. Algo a se notar é que, em todos os casos mencionados, a soma dos dígitos será 9, já que um número e seu reverso possuem os mesmos algarismos, e portanto a mesma soma dos algarismos, que irá se anular, e o 9 tem peso nulo na soma de algarismos. Isso se aplica a qualquer situação. Por exemplo, 2394919491 -> 9999443211 - 1123449999 = 8875993212, cuja soma final dos algarismos é 9.

Voltando a um dos exemplos da sua mensagem inicial:

Por exemplo se a senha for 050 basta apenas 1 passo: 500 - 005 = 495

Se continuássemos, teríamos 954 - 459 = 495.

Em todos os exemplos com 3 dígitos, chegaremos a esta operação:
954 - 459 = 495

Da mesma forma, com 4 dígitos, sempre chegaremos a esta operação:
7641 - 1467 = 6174

Notemos que nos dois casos todos os componentes  da operação apresentam os mesmos dígitos. No primeiro caso (4, 5, 9); no segundo caso (1, 4, 6, 7).

Daí, o mais importante, é que sempre chegaremos a um ciclo. Ou seja, se eu reordenar qualquer número formado pelos algarismos (4, 5, 9) em ordem decrescente e subtrair desse resultado o número formado pela ordem crescente, o resultado será
495 (que é apenas uma das permutações). Ou seja, não tem mais como sair daí. O mesmo acontece com os algarismos (1, 4, 6, 7), que formarão o 6174.

Daí, uma questão interessante seria: Existem mais números de 3 ou 4 algarismos com essa propriedade (a subtração das suas permutações ordenadas resulta em uma das suas permutações)?

A resposta é quase que um não. Fiz um código que passa por todos esses números (de 100 a 9999) e verifica se cada um possui essa propriedade. Obtive os seguintes números:

Código:

459
495
549
594
945
954
1467
1476
1647
1674
1746
1764
4167
4176
4617
4671
4716
4761
6147
6174
6417
6471
6714
6741
7146
7164
7416
7461
7614
7641

Como podem notar, todos os números de 3 algarismos são formados pelos dígitos (4, 5, 9) e todos os números de 4 algarismos são formados pelos dígitos (1, 4, 6, 7). A ordenação destes sempre será a mesma, logo sempre vamos cair nos ciclos que mencionei. Por exemplo, para o 6147 (e todos os outros de 4 dígitos), teríamos 7641 - 1467 = 6174.

Uma outra ideia interessante é a seguinte: Como existem apenas esses números com essa propriedade, então, caso seja possível provar que as operações de subtração mencionadas no desafio sempre irão percorrer todos os dígitos, fica lógico afirmar que em algum momento essas combinações serão percorridas e chegaremos nos ditos números mágicos.

Pensando ainda em generalizações, se imaginarmos o mesmo para números de mais dígitos, seria possível então encontrar, para uma mesma quantidade de dígitos, mais de um grupo de dígitos com a propriedade de a subtração resultar em uma de suas permutações? Se a resposta for sim, então temos a seguinte situação: Ao realizar as operações descritas no desafio, em algum momento poderíamos chegar em um desses grupos de dígitos e ficarmos travados no mesmo. No entanto, se houver (mas não apenas se houver), para uma mesma quantidade de dígitos, mais de um grupo de dígitos com a propriedade, então nenhuma será mágica, pois ficaríamos travados em alguma dessas em cada ocasião. Nos casos de 3 e 4 dígitos, visto que não existem outras combinações com a propriedade, repito: basta apenas verificar a proposição de que todas as combinações de dígitos serão percorridas, para então verificarmos que chegaremos nos ditos números mágicos.

Vamos então olhar para números com mais de 4 dígitos. Com as ideias acima e auxílio computacional a partir do código que elaborei, encontrei vários outros números.

Para o caso de 6 dígitos, verifiquei que existem 360 permutações de (1, 3, 4, 6, 6, 7) e 90 permutações de (4, 5, 9). E estas são todas as que existem para 6 dígitos. Para o primeiro grupo, o resultado é sempre 631764; para o segundo, é sempre 549945. Curiosamente, os dígitos 0, 2 e 8 não aparecem nem sequer em uma das vezes. Destes exemplos, vemos que não é possível haver um número mágico com 6 dígitos, visto que há dois casos cíclicos.

Diante disso, vemos que temos casos cíclicos, isto é, quando, para um grupo de dígitos, a subtração de duas de suas permutações resulta em uma de suas permutações, e daí não é mais possível sair do respectivo ciclo.

Se houvesse mais de um caso assim para 3 ou 4 dígitos, os números 495 e 6174 não seriam números mágicos, e poderíamos, com as subtrações, entrar em um ciclo diferente dos ciclos dos dois.

Estou computando todos os números que se encaixam nessas condições com até 20 dígitos. Até agora cheguei em 9 dígitos, e não consigo estimar ainda quanto tempo levará até o final. Farei um tratamento dos resultados obtidos para tentar extrair mais informações ou verificar a existência de mais casos únicos (e consequentemente mágicos) para as diferentes quantidades de dígitos.

Estou também tentando verificar se é possível provar, nos casos de 3 e 4 dígitos, que, para qualquer número inicial, as subtrações sucessivas irão sempre percorrer todas as combinações de dígitos, e, com isso, provar o desafio.

EDITADO:
O zero é uma exceção interessante. Para qualquer número de dígitos, as operações com os números capícuas resultam em zero. Não fosse a exceção do desafio, não existiriam números mágicos, já que existe mais de um grupo de dígitos que formam um ciclo infinito. Por exemplo, o 495 dividiria espaço com o 000 entre os números de 3 dígitos que podem formar um ciclo. Assim como o 6174 dividiria espaço com o 0000.
000-000=000
0000-0000=0000

Consegui verificar, por análise matemática, que as subtrações envolvendo 3 dígitos sempre chegarão em algum momento no 495, e consequentemente ficarão presas nele. Como estou editando de madrugada, amanhã ou em breve passarei as demonstrações a limpo.

Meu caro Pedro

Eu o admiro pela sua competência e tenacidade. Você não desiste nunca!
Eu não tinha pensado em usar computação para pesquisar outros eventuais números mágicos.
Vou aguardar, ansioso, pelos próximos capítulos da sua odisseia.
Se for coroada de êxito, prometo acompanhar você na apresentação num futuro congresso mundial de matemática. kkkkk

Elcio, seria uma grande honra. Aliás, o seu desafio me deixou curioso por muito tempo.

Vou compartilhar a solução a que cheguei até o momento para a primeira parte: o caso de 3 algarismos. Vamos lá.

Condições impostas pelo desafio:
- Os três algarismos não são todos iguais.

Partindo de qualquer número de 3 algarismos (não todos iguais), digamos (x, y, z), definamos os algarismos (a, b, c) da seguinte forma:  a é o maior entre (x, y, z), b é o segundo maior, c é o menor. Assim, ao reescrever (x, y, z) em ordem decrescente temos (a, b, c), e em ordem crescente, temos (c, b, a). Uma primeira constatação é que a > c, pois os 3 algarismos não são todos iguais.

Seguindo o fluxo do desafio, temos que subtrair (c, b, a) de (a, b, c).
 a b c
- c b a
----------
(a - c -1), ((10 + b - 1) - b), (10 + c - a)

Obs: Na subtração, como c < a, o c tem que "pegar emprestado" do b. Depois, como b - 1 < b, o b tem que pegar emprestado do a.

Simplificando a segunda expressão, temos:
(a - c -1), 9, (10 + c - a)

Visto que (a, b, c) são algarismos e a > c, teremos apenas os casos a seguir. Vamos avaliar o resultado da expressão acima em cada caso.

I)  a - c = 1 --> 099
II)  a - c = 2 --> 198
III)  a - c = 3 --> 297
IV)  a - c = 4 --> 396
V)  a - c = 5 --> 495
VI)  a - c = 6 --> 594
VII)  a - c = 7 --> 693
VIII)  a - c = 8 --> 792
IX)  a - c = 9 --> 891

Repetindo sucessivamente a subtração entre os números obtidos em ordem decrescente e os números obtidos em ordem crescente, teremos:

I)  990 - 099 = 891 -> 981 - 189 = 792 -> 972 - 279 = 693 -> 963 - 369 = 594 -> 954 - 459 = 495
II)  981 - 189 = 792 -> 972 - 279 = 693 -> 963 - 369 = 594 -> 954 - 459 = 495
III)  972 - 279 = 693 -> 963 - 369 = 594 -> 954 - 459 = 495
IV)  963 - 369 = 594 -> 954 - 459 = 495
V)  954 - 459 = 495
VI)  954 - 459 = 495
VII)  963 - 369 = 594 -> 954 - 459 = 495
VIII)  972 - 279 = 693 -> 963 - 369 = 594 -> 954 - 459 = 495
IX)  981 - 189 = 792 -> 972 - 279 = 693 -> 963 - 369 = 594 -> 954 - 459 = 495

OBS: Podemos notar repetições das operações entre os pares que somam 11.

Vemos que, para um número de 3 algarismos (não todos iguais), por exemplo, 349, se calcularmos a diferença entre o maior e o menor algarismo (neste caso, 6), conseguiremos saber quantas operações de subtração serão necessárias até chegarmos ao 495. O algarismo central será irrelevante.

A ideia que facilita aqui é que conseguimos representar todos os casos de números de 3 algarismos com apenas 9 casos, visto que, ao ordenarmos os números e subtrair, teremos apenas 9 casos distintos.

Parte desta propriedade eu já conhecia, desde garoto (Desafio da Marta Rocha):

Dada uma centena qualquer abc (com a > c)
A centena invertida é cba

A diferença ∆ = abc - cba tem as seguintes propriedades:

1) O algarismo do meio de ∆ é sempre 9
2) A soma dos algarismos extremos de ∆ é sempre 9

Ex.: Para abc = 731 ---> cba = 137 ---> ∆ = 731 - 137 ---> ∆ = 594

Algarismo do meio = 9

Soma dos extremos = 5 + 4 = 9

E esta propriedade é facil de ser provada:

abc = a.100 + b.10 + c = (a - 1).100 + 100 + b.10 + c = (a - 1).100 + 90 + 10.b + 10 + c --->

abc = (a - 1).100 + 90 + 10.b + 10 + c ---> I

cba = c.100 + b.10 + a ---> II


I - II = (a - c - 1).100 + 90 + (10 + c - a) = (a-c-1)9(10+c-a) ---> Algarismo do meio = 9

Soma dos extremos ---> S = (a - c - 1) + (10 + c - a) ---> S = 9