In un articolo su Il Post si discuteva di un indovinello. Nei commenti all’articolo si faceva cenno ad un’altro indovinello della stessa categoria. Facendo una breve ricerca in rete ho trovato una trattazione del problema nientedimeno che da parte di E.W.Dijkstra. La soluzione è sicuramente la più elegante e rigorosa tra quelle che si possono trovare in rete, che spesso non si capisce bene il passo da un passaggio e l’altro. Mi è quindi sembrato un buon esercizio per rinfrescare le mie conoscenze di F# tentare di svolgere i passaggi matematici della soluzione in F# appunto. Ma prima riassumiamo il problema come descritto nella soluzione di Dijkstra.
Ci sono tre persone, Cheryl sceglie due numeri nell’intervallo [2..99], poi comunica a Paul il prodotto di questi numeri, mentre a Sam viene comunicata la somma dei due numeri. A questo punto si svolge il seguente dialogo:
Paul: non conosco i due numeri;
Sam: lo sapevo già;
Paul: allora adesso so quali sono i due numeri;
Sam: allora anch’io adesso so quali sono;
A questo punto ci viene chiesto di determinare i due numeri, è stabilire che la soluzione sia unica.
Dalla prima affermazione di Paul possiamo deudurre che:
- il prodotto non è il prodotto di due numeri primi;
e dal fatto che, inoltre, i fattori devono essere minori di 99, segue che il prodotto non può contenere fattori primi>= 50, o poiché 53 è il più piccolo numero primo >=50 ( questo perché banalmente 50*2=100>99)
2. il prodotto non contiene fattori >=53
Poiché Sam sa anche lui prima di qualsiasi informazione da parte di Paul che Paul non può determinare i due fattori, la somma dei due numeri deve essere tale che le proprietà 1 e 2 possono essere dedotte dalla loro somma. La proprietà 1 esclude tutte le somme che possono essere scritte come la somma di due numeri primi. La congettura di Goldbach (grandioso! ndt) dice che tutti i numeri pari >=4 possono essere scritti come somma di due numeri primi, esclude tutti i numeri pari per la somma (se non è dato nessun limite superiore per i numeri). Se un numero dispari può essere scritto come somma di due numeri primi, uno di essi deve essere pari, ossia 2, e quindi sapere che la somma è un numero non primo +2 è sufficiente per garantire la proprietà 1. Per garantire la proprietà 2 la somma deve essere <=54.
Ora dalla prima risposta di Sam deriva che la somma è un numero non primo + 2 e <=54. Chiamiamo questo insieme S0.
Dijkstra determina l’insieme a mano, io ho cercato di determinarlo con F#. Per eseguire il programma ho utilizzato l’ottimo LINQPad, che a dispetto del nome serve ad eseguire in maniera immediata pezzi di codice scritti non solo in LINQ ma in uno dei vari linguaggi disponibili per .NET, anche F#. Quindi installatelo immediatamente, può tornare sempre utile. Quindi apriamo un nuovo documento in LINQPad e impostiamo il linguaggio a F# program. Poi scriviamo il seguente codice:
[code language=”fsharp”]// crivello di Eratostene per i numeri primi da [a..b]
let rec sieve = function
| (p::xs) -> p :: sieve [ for x in xs do if x % p > 0 then yield x ]
| [] -> []
//controlla se il numero e nella lista
let containsNumber number list = List.exists (fun elem -> elem = number) list
//lista dei numeri primi da 2 a 53
let primes = sieve [2..53]
//test se pari o dispari
let rec even n = n = 0 || odd (abs n – 1)
and odd n = n <> 0 && even (abs n – 1)
//finalmente il nostro insieme
let S0= [ for a in 2 .. 53 do
if odd a && a+2<54 && not (containsNumber a primes) then yield ( a+2 ) ]
S0.Dump("Insieme di test")
[/code]
Eseguendo questo pezzo di codice viene stampato l’insieme S0 = {11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53}, esattamente lo stesso presente nell’articolo di Dijkstra, quindi fino a qui ci siamo.
Torniamo al ragionamento di Dijkstra:
Dopo la prima risposta di Sam, Paul sa che la somma dei due fattori deve appartenere all’insieme S0. Se Paul è più intelligente di quello che siamo stati, lui forse potrebbe concludere che la soma appartiene ad un insieme più piccolo, ma non può essere più intelligente di quello che sono stato, io non ho altra scelta che assumere che Paul potrebbe determinare i fattori del prodotto attraverso conoscenze aggiuntive che la loro somma appartiene a S0.
Paul non può determinare i fattori se il loro prodotto può essere scritto in più di un modo come x*y, in modo tale che x+y appartiene a S0. Potrebbe, per esempio, essere disorientato dal prodotto = 30, perché 6+5=11 e 2+15=17. Paul, tuttavia, ha un compito particolarmente facile se il prodotto è (numero primo * potenza di 2): poiche tutti gli elementi di S0 sono dispari, uno dei fattori deve essere dispari ( ad esempio un numero primo), l’altro deve essere pari ( cioè una potenza di 2).
Quindi se il prodotto era 24, Paul concluderebbe immediatamente 3*8, se fosse 28, Paul concluderebbe immediatamente 7*4. Poiché 3+8=7+4=11 nel caso della somma = 11, Sam non potrebbe mai fare l’affermazione finale che anche lui conosce i due numeri! Quindi, in considerazione della seconda risposta data da Sam, noi (ma non Paul quando da la seconda risposta) possiamo cancellare da S0 tutti i valori come 11 che possono essere scritti come un numero primo+ una potenza di 2.
Quindi torniamo al nostro programma F# e sfoltiamo l’insieme S0.
[code language=”fsharp”]
(*
determiniamo S1 eliminiamo da S0 tutti valori che possono essere scritti
come una potenza di 2^x + numero primo
x>1
la funzione dato un itero y determina per quante x y= 2^x+numero primo per x>1
è facile filtrare la lista S0 per ottenere S1
*)
let s2p2 n =
let rec loop c p =
if c>p then 0
elif (containsNumber (p-c) primes) then 1 + loop (c*2) p
else 0 + loop (c*2) (p-c)
loop 4 n
let S1=S0
|> List.filter ( fun x -> (s2p2 x)=1)
S1.Dump("somme che possono essere scritti come 2^x+numero primo e x>")
[/code]
Questo programma ci da l’insieme S1={17,29,41,53}.
Esaminando le 4 possibilità a turno:
somma = 17
2 * 15 = 6 * 5 rigettato perché 6 + 5 = 11 è in S0
3 * 14 = 2 * 21 rigettato perché 2 + 21=23 è in S0
4 * 13 decidibile per Paul
5 * 12 = 3 * 20 rigettato perché 2 + 35 = 37 è in S0
6 * 11 = 2 * 33 rigettato perché 3 + 24 = 27 è in S0
7 * 10 = 2 * 35 rigettato perché 2 + 35 = 37 è in S0
8 * 9 = 3 * 24 rigettato perché 3 +24 = 27 è in S0
Poiché il caso della somma 17 fornisce solo un caso che è decidibile per Paul su quali siano i fattori, la coppia (4, 13) è una soluzione. Per mostrare che questa soluzione è unica, è sufficiente mostrare che per ogni caso, dei tre rimanenti, in S1 almeno uno degli altri casi decidibili esistono affiancati a 16 * 13, 4 * 37m e 16 * 37 rispettivamente.
somma = 29
4 * 25 = 20 * 5 decidibile per Paul (come 4 * 25) perché 20+5=25 che non è in S0
somma = 41
3 * 38 = 2* 57 = 6 * 19 decidibile per Paul (come 3 *38) perch* ne 2 +57=59 ne 6+19=25 sono in S0
somma = 53
6*47=2*141=3*94 decidibile per Paul (come 6 * 47) perché ne 2+141=143 ne 3+94=97 sono in S0
Quindi Sam non può giustificare la sua seconda risposta per 29, 41, o 53, per cui è dimostrata l’unicità della soluzione.