Generalizzazione sui quadrati concatenabili
Salve, giorni fa ho letto uno dei problemi proposti nei giochi matematici della Bocconi (trattato anche qui https://www.matematicamente.it/forum/viewtopic.php?t=219228&p=8538621): si chiedeva, a partire dai quadrati di numeri interi aventi 3 cifre, il numero massimo s di quadrati concatenabili, ovvero tali che l'ultima cifra di uno fosse la prima cifra del seguente. Per n = 3 è facile dimostrare che s = 12, e una delle possibili catene è {841, 121, 144, 484, 441, 169, 961, 196, 676, 625, 529, 900} (ce ne sono 26 possibili).
È immediato constatare che per
n = 1 -> s = 1
n = 2 -> s = 4
Ora mi è venuta la malsana idea di generalizzare il risultato con n > 3
Ho provato con delle righe di codice di Mathematica, funzionano fino n = 3, ma per numeri maggiori il sistema si rallenta a tal punto da non produrre alcunché.
Ho quindi effettuato delle prove e per n = 4 la catena più lunga che ho trovato è composta da s = 30 elementi
{2025, 5776, 6561, 1225, 5625, 5041, 1369, 9801, 1024, 4624, 4489, 9216, 6084, 4761, 1521, 1764, 4356, 6889, 9604, 4225, 5329, 9409, 9025, 5184, 4096, 6241, 1681, 1156, 6724, 4900}
Invece per n = 5 la catena più lunga che ho trovato è composta da s = 93 elementi
{39204, 47089 ,97344, 46225, 53824, 41616, 66564, 42025, 51984, 43681, 12544, 48841,13225, 52441, 18225, 58081, 10609, 96721, 10404, 45369, 93025, 56644, 47524, 41209, 91809, 93636, 62001, 10816, 65536, 67081, 16641, 10201, 12321,14641, 19321, 13689, 98596, 66049, 95481, 17161, 15129, 94864, 44944, 43264, 47961, 18496, 63504, 49729, 94249, 90601, 13456, 64009, 99225, 53361, 15625, 55696, 69696, 68121, 14161, 11881, 19881, 18769, 97969, 99856, 61009, 92416, 60516, 60025, 57121, 11025, 55225, 50625, 58564, 42436, 68644, 40401, 14884, 45796, 63001, 11664, 46656, 65025, 51076, 69169, 91204, 44521, 17956, 64516, 61504, 40804, 49284, 42849, 96100}
Speravo di trovare un pattern in questi valori, ma l'unico che ho trovato è https://oeis.org/A148187 e non risponde alla mia domanda, perché i valori dentro quella sequenza crescono più rapidamente del numero di quadrati aventi n cifre e ovviamente s deve essere inferiore a tale valore.
Qualche idea?
È immediato constatare che per
n = 1 -> s = 1
n = 2 -> s = 4
Ora mi è venuta la malsana idea di generalizzare il risultato con n > 3
Ho provato con delle righe di codice di Mathematica, funzionano fino n = 3, ma per numeri maggiori il sistema si rallenta a tal punto da non produrre alcunché.
Ho quindi effettuato delle prove e per n = 4 la catena più lunga che ho trovato è composta da s = 30 elementi
{2025, 5776, 6561, 1225, 5625, 5041, 1369, 9801, 1024, 4624, 4489, 9216, 6084, 4761, 1521, 1764, 4356, 6889, 9604, 4225, 5329, 9409, 9025, 5184, 4096, 6241, 1681, 1156, 6724, 4900}
Invece per n = 5 la catena più lunga che ho trovato è composta da s = 93 elementi
{39204, 47089 ,97344, 46225, 53824, 41616, 66564, 42025, 51984, 43681, 12544, 48841,13225, 52441, 18225, 58081, 10609, 96721, 10404, 45369, 93025, 56644, 47524, 41209, 91809, 93636, 62001, 10816, 65536, 67081, 16641, 10201, 12321,14641, 19321, 13689, 98596, 66049, 95481, 17161, 15129, 94864, 44944, 43264, 47961, 18496, 63504, 49729, 94249, 90601, 13456, 64009, 99225, 53361, 15625, 55696, 69696, 68121, 14161, 11881, 19881, 18769, 97969, 99856, 61009, 92416, 60516, 60025, 57121, 11025, 55225, 50625, 58564, 42436, 68644, 40401, 14884, 45796, 63001, 11664, 46656, 65025, 51076, 69169, 91204, 44521, 17956, 64516, 61504, 40804, 49284, 42849, 96100}
Speravo di trovare un pattern in questi valori, ma l'unico che ho trovato è https://oeis.org/A148187 e non risponde alla mia domanda, perché i valori dentro quella sequenza crescono più rapidamente del numero di quadrati aventi n cifre e ovviamente s deve essere inferiore a tale valore.
Qualche idea?
Risposte
Il problema e' equivalente a cercare il percorso piu' lungo in un grafo orientato con cicli.
https://en.wikipedia.org/wiki/Longest_path_problem
...the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP.
Grazie Quinzio! Stavo considerando se potesse essere un problema affine a questo https://en.m.wikipedia.org/wiki/Maximum_flow_problem e nel caso se si potesse implementare uno dei relativi algoritmi di risoluzione.
Il codice che hai creato per il caso n=3 riesce a stabilire il massimo anche per n=4 o n=5?
Il codice che hai creato per il caso n=3 riesce a stabilire il massimo anche per n=4 o n=5?
Questo è il grafo che rappresenta n=4
"ulissex":
Grazie Quinzio! Stavo considerando se potesse essere un problema affine a questo https://en.m.wikipedia.org/wiki/Maximum_flow_problem e nel caso se si potesse implementare uno dei relativi algoritmi di risoluzione.
Il codice che hai creato per il caso n=3 riesce a stabilire il massimo anche per n=4 o n=5?
Ciao, scusa se rispondo solo ora.
Da quello che ho visto, con n=4 o 5 il tempo necessario per esplorare tutti i percorsi inizia a diventare proibitivo.
Non so se si riesce ad ottimizzare ulteriormente l'algoritmo.
Per il momento non ci sto lavorando.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo