Newsgroup: it.hobby.enigmi
Titolo: La tavola dei coprimi

La seguente tabellina e' cosi' composta: sulla diagonale principale sono
messi i numeri naturali, ed agli incroci c'e' ZERO se i due numeri sono
primi fra loro, altrimenti c'e' UNO. Naturalmente la tabellina si
intende estesa all'infinito.
 
                    .
                  .
                9 . .
              8 0 . .
            7 0 0 . .
          6 0 1 1 . .
        5 0 0 0 0 . .
      4 0 1 0 1 0 . .
    3 0 0 1 0 0 1 . .
  2 0 1 0 1 0 1 0 . .
1 0 0 0 0 0 0 0 0 . .
a) Dove sara' il primo ZERO con 4 UNO nelle caselle adiacenti?
b) Dove sara' il primo UNO  con 4 UNO nelle caselle adiacenti?
c) Dove sara' il primo ZERO circondato da 8 UNO?
d) Dove sara' il primo UNO circondato da 8 ZERI?
e) Dove sara' il primo UNO circondato da 8 UNO?
:) dario

 ...
Mi chiedo però una cosa, caro Dario...
Quando proponi questi problemi, come ti aspetti che vengano risolti? Con al
forza bruta del calcolatore o con il fino ragionamento?
In particolare, tu come ci sei arrivato per crearli e trovare le soluzioni
alle tue domande?
Sai, m'è venuto in mente guardando il tuo problema precedente. Io l'ho
risolto col ragionamento, poi ho visto il post di Massimo Mondò che l'ha
risolto calcolando.
Questo problema poi sembra destinato ad essere risolto per via
programmatoria.
Ora, quando si trattasse di questo, io mi astengo. Non perché non sappia
programmare (anzi, direi che lo so fare con cognizione di causa), ma perché,
francamente, non ho voglia né tempo di scrivere un programma per farlo...
E (piccola nota polemica, ma non volermene...), sinceramente, non vedo dove
ci possa essere il divertente nello scrivere un programma che verrà eseguito
una sola volta (a parte il debug) e poi passerà nel dimenticatoio dopo aver
fornito il risultato in un tempo si suppone breve.
Ho sempre letto con interesse i problemi che spesso poni (sei decisamente
vulcanico!), e mi diverte discuterne anche con altri miei amici. Però non
posso farlo se si tratta di calcolare... :-\
Pensa che solo 20 anni fa per certi problemi trovare la soluzione sarebbe
stata un'impresa improba, e che ancora oggi (purtroppo) non tutti dispongono
di un computer... Come l'avrebbe risolto questo tuo problema un tipo come,
che so, Pierre de Fermat?
Certo che la Matematica è cambiata, con l'avvento dei computer... In maniera
che anche a me sfugge, io che ho avuto la fortuna di giochicchiare con un
computer da quando avevo 6 anni...
Si parla tanto dell'inutilità odierna delle dimostrazioni matematiche per i
problemi recenti, ma ancora non riesco a vedere come un computer possa
aiutarci quando si tratta di lavorare a tu per tu con l'infinito.
Per gli enigmi è la stessa cosa?
Ovviamente, questo enigma che hai posto fermerà un programma dopo un numero
finito di cicli, anche perché suppongo che tu le risposte le sappia già. Ma
se invece non le sapessi, e l'avessi buttata lì per vedere cosa sarebbe
successo? In questo caso, forse, non c'è risposta a qualche tua domanda: il
computer andrebbe avanti all'infinito...
Scusa, magari sto dicendo delle sciocchezze, il fatto è che sono
perplesso...
MaxArt
P.S.: sinceramente non capisco cosa tu intenda per il "primo" zero o uno...
come dobbiamo ordinarli? Per colonna o per riga? O per somma di riga e
colonna?

 MaxArt
Ciao :)
MArco

 fornito il risultato in un tempo si suppone breve.
Personalmente lo trovo estremamente eccitante, e non ho nessuna pena per i
poveri algoritmi, nati e morti nell'arco di un post. Certo, se è banale
brute force che in 2 minuti (per la stesura) risolve, allora neanche io mi
ci applico piu` di tanto, ma la soddisfazione di veder girare il giocattolo
dopo poche (o magari moltissime...) prove è grande. Soprattutto quando nella
finestra di debug vedi i risultati saltar fuori insopportabilmente lenti, e
poi rincorrersi velocissimi dopo aver messo mano al codice (lo dicevo, che
con un controllo in testa al ciclo...). E poi, il pensiero creativo e`
indispensabile sia per la soluzione manuale che per quella automatica. Se la
scintilla non arriva, ci si pianta, in un caso come nell'altro. Questione di
gusti e di attitudini: Dario fa uno schemino ordinato, Paolo comincia con
una tabella di Excel, altri ci mettono le x e le y e altri ancora vanno a
tentativi. L'importante è arrivare.
Ciao, Silv:o)

Per ora provo alcune soluzioni parziali
Dati due numeri a,b, la zona di incrocio conterra' i nove valori
(a+1;b-1).(a+1;b).(a+1;b+1)
.(a;b-1)...(a;b)...(a;b+1)
(a-1;b-1).(a-1;b) (a-1;b+1)
dove ciascuna espressione tra parentesi vale 0 o 1, a seconda che i due
termini siano o meno coprimi
a) Dove sara' il primo ZERO con 4 UNO nelle caselle adiacenti?
* 1 *
1 0 1
* 1 *
a,b devono essere coprimi;
scelgo a pari e b dispari;
essendo (b-1) e (b+1) pari e' verificata la condizione di due 1 a
destra e a sinistra nella riga centrale;
per ottenere due 1 in alto e in basso nella colonna centrale, pongo la
condizione che b sia il prodotto di due numeri primi
b=p1*p2
e che (a-1) e (a+1) siano divisibili rispettivamente per p1 e p2
provo con p1=3, p2=5, b=15
e trovo immediatamente
a=4, a-1=3, a+1=5 che verificano quanto richiesto
d) Dove sara' il primo UNO circondato da 8 ZERI?
0 0 0
0 1 0
0 0 0
per il momento trovo la condizione (necessaria, ma non sufficiente) che
a,b siano entrambi multipli di 6.
Infatti ciascuna delle terne (a-1,a,a+1) e (b-1,b,b+1) contiene un
multiplo di 3 ed almeno un numero pari.
Gli incroci tra due multipli di 3 o tra due pari generano un valore 1,
pertanto e' necessario che tali incroci cadano nella casella centrale,
quindi a,b sono entrambi pari e multipli di 3.
ciao
paolo
Sent via Deja.com 
http://www.deja.com/
Before you buy.

 colonna?
Ho riportato le domande del proponente, immagino che intenda il primo
caso che si incontra facendo crescere la tabella, aggiungendo ogni volta
l'intero successivo.
ciao :) dario

 per il momento trovo la condizione (necessaria, ma non sufficiente)
che  a,b siano entrambi multipli di 6.
Un'altra condizione, questa volta sufficiente, e' che a-1, a+1, b-1,
b+1 siano primi.
Guarda caso, 5,7,11,13 lo sono, quindi
a=6 ; b=12 e' la soluzione.


 tentativi. L'importante è arrivare.
Io non capisco sinceramente l'uso di Excel per queste cose... :-)
Ci sono programmi come MatLab, ad esempio, che trovo più adatti, o anche
solo il Basic.
MaxArt

 solo il Basic.
Ma se è l'unico prodotto valido di tutto il paccheto Office!
Io sinceramente lo trovo utilissimo e versatile: scrivi le formule, "tiri
giù", letteralmete, col mouse sull'angolino, e hai riempito una tabella.
Quasi sempre osservando i dati l'idea viene da sè. E poi ha un ottimo editor
per visual basic, che di per se è un linguaggio adatto a questi usi, grazie
al debug "on fly" ed alla semplicità di utilizzo. Se ci metti che da Excel
puoi usare anche le funzioni interne ed i fogli di lavoro per scaricare i
dati, ecco che hai uno strumento pratico e veloce. E' chiaro che se
programmi in C o in Pasquale è meno efficace.
Ma stiamo scivolando nell'OT, temo.
Ciao, Silv:o)

 
A chi lo dici. TEXAS TI 994A 16 K di memoria !!!
CiaO,
Massimo

 c) Dove sara' il primo ZERO circondato da 8 UNO?
   |a-1| a |a+1|
---+---+---+---+
b-1| 1 | 1 | 1 |
---+---+---+---+
.b | 1 | 0 | 1 |
---+---+---+---+
b+1| 1 | 1 | 1 |
---+---+---+---+
Con a e b dispari i 4 angoli sono automaticamente UNO. Veniamo ai 4 UNO
centrali.
Intanto notiamo che a e b non possono essere primi. Infatti se a fosse primo
allora a|(b-1) (a divide b-1) e a|(b+1) quindi a|2b , a|b contro l'ipotesi a
e b coprimi. Stessa cosa per b
Allora a=kp e b=hq, con p e q primi e k ed h dispari
Qui finisce il rigore e cominciano i tentativi. Con a=3*7 trovo che
a-1=20=5*4
a+1=22=2*11
Dato che b deve avere fattori comuni con entrambi e deve essere dispari, ho
provato b=5*11=55. Per fortuna
b-1=54=3*17
b+1=56=7*8
ed entrambi hanno fattori in comune col 21. Quindi
   |20 |21 |22 |
---+---+---+---+
54 | 1 | 1 | 1 |
---+---+---+---+
55 | 1 | 0 | 1 |
---+---+---+---+
56 | 1 | 1 | 1 |
---+---+---+---+
Ciao, Silv:o

 Ma stiamo scivolando nell'OT, temo.
Ma chi se ne importa, una volta ogni tanto... ;-)
MaxArt