La stringa 1...17 e le sue permutazioni.
La stringa 1...17 e le sue permutazioni.
Siano $ n $ un intero positivo e $ P $ l'insieme di tutte le possibili permutazioni della stringa decimale $ 1\ldots 17 $ contenente esattamente una cifra pari a 7 ed (n-1) cifre pari ad 1. Determinare ogni possibile valore di n tale che P contenga unicamente numeri primi in forma decimale. (IMO shortlist 1990)
[parac**o]
L'ho risolto davvero? Spero di no, così imparo qualcosa
[/parac**o]
Ok, procediamo (molto timorosamente)...
Innanzitutto dobbiamo escludere tutti gli $ \displaystyle n\equiv 0, 3 (mod 6) $, altrimenti ogni numero sarebbe divisibile per 3.
Provo gli $ n $ *stupidi*:
$ \displaystyle n-1=0,\ n=1: P= \{7\} $
$ \displaystyle n-1=1,\ n=2: P=\{17, 71\} $.
Finora abbiamo avuto tutti primi
Procediamo:
$ \displaystyle n-1=3,\ n=4: P=\{1117, 1171, 1711, 7111\} $.
Fidandomi ciecamente di Ossido (e sfruttando i "poteri" della calcolatrice)
, so che $ \displaystyle 7111 = 13*547 $ e che $ 111111 = 3*7*11*13*37 $.
Siccome sia 7111, sia 111111 sono divisibili per 13, abbiamo che tutte le P contenenti $ \displaystyle n=4+6k,\ \Leftrightarrow n\equiv 4 (mod 6) $, non soddisfano la proprietà. Continuiamo con il caso seguente:
$ \displaystyle n-1=4,\ n=5: P=\{11117, 11171, 11711, 17111, 71111\} $.
Fra questi numeri dobbiamo trovare multipli di 7 o di 13, per poter ripetere lo stesso discorso, e abbiamo $ \displaystyle 11711 = 7*7*239 $. Così si può, come prima, generalizzare escludendo gli $ \displaystyle n=5+6k \Leftrightarrow n\equiv 5 (mod 6) $, che sono numeri chiaramente non primi. Ora:
$ \displaystyle n-1=6, \ n=7: P=\{1111117, 1111171, 1111711, $$ 1117111, 1171111, 1711111, 7111111\} $. Senza scervellarsi troppo, sappiamo che $ \displaystyle 7|111111 $, quindi P contenenti 7111111 e i suoi derivati, ovvero $ n $ della forma $ \displaystyle 1+6k \Leftrightarrow n\equiv 1(mod 6) $ non vanno accolte. In ultimis:
$ \displaystyle n-1=7, \ n=8: P=\{11111117, 11111171, $$ 11111711, 11117111, 11171111, 11711111, 17111111, 71111111\} $. Beh, ora ci tocca solo fare un po' di divisioni e scoprire il numero divisibile per 13...trovato! Ed è 11111711, posso dunque escludere gli $ \displaystyle n=8+6k \Leftrightarrow n\equiv 2(mod 6) $.
Con questo, ho concluso i casi (ricordo che sono soluzioni n=1 e n=2) e, che dire, spero che HiT non sia troppo crudele con me
L'ho risolto davvero? Spero di no, così imparo qualcosa
[/parac**o]
Ok, procediamo (molto timorosamente)...
Innanzitutto dobbiamo escludere tutti gli $ \displaystyle n\equiv 0, 3 (mod 6) $, altrimenti ogni numero sarebbe divisibile per 3.
Provo gli $ n $ *stupidi*:
$ \displaystyle n-1=0,\ n=1: P= \{7\} $
$ \displaystyle n-1=1,\ n=2: P=\{17, 71\} $.
Finora abbiamo avuto tutti primi
Procediamo:$ \displaystyle n-1=3,\ n=4: P=\{1117, 1171, 1711, 7111\} $.
Fidandomi ciecamente di Ossido (e sfruttando i "poteri" della calcolatrice)
, so che $ \displaystyle 7111 = 13*547 $ e che $ 111111 = 3*7*11*13*37 $.Siccome sia 7111, sia 111111 sono divisibili per 13, abbiamo che tutte le P contenenti $ \displaystyle n=4+6k,\ \Leftrightarrow n\equiv 4 (mod 6) $, non soddisfano la proprietà. Continuiamo con il caso seguente:
$ \displaystyle n-1=4,\ n=5: P=\{11117, 11171, 11711, 17111, 71111\} $.
Fra questi numeri dobbiamo trovare multipli di 7 o di 13, per poter ripetere lo stesso discorso, e abbiamo $ \displaystyle 11711 = 7*7*239 $. Così si può, come prima, generalizzare escludendo gli $ \displaystyle n=5+6k \Leftrightarrow n\equiv 5 (mod 6) $, che sono numeri chiaramente non primi. Ora:
$ \displaystyle n-1=6, \ n=7: P=\{1111117, 1111171, 1111711, $$ 1117111, 1171111, 1711111, 7111111\} $. Senza scervellarsi troppo, sappiamo che $ \displaystyle 7|111111 $, quindi P contenenti 7111111 e i suoi derivati, ovvero $ n $ della forma $ \displaystyle 1+6k \Leftrightarrow n\equiv 1(mod 6) $ non vanno accolte. In ultimis:
$ \displaystyle n-1=7, \ n=8: P=\{11111117, 11111171, $$ 11111711, 11117111, 11171111, 11711111, 17111111, 71111111\} $. Beh, ora ci tocca solo fare un po' di divisioni e scoprire il numero divisibile per 13...trovato! Ed è 11111711, posso dunque escludere gli $ \displaystyle n=8+6k \Leftrightarrow n\equiv 2(mod 6) $.
Con questo, ho concluso i casi (ricordo che sono soluzioni n=1 e n=2) e, che dire, spero che HiT non sia troppo crudele con me
Tu chiamale, se vuoi, emozioni.