[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Ricreazioni di Settembre 2002

270. Il contadino e le galline
di Mirko Segatello
Un povero contadino ha un pollaio con alcune galline. La prima sera ne mangia una ma la notte un lupo ne mangia 1/4. La sera seguente ne compera 5 e le aggiunge al pollaio ma durante la notte il solito lupo ne mangia 1/4. La terza sera il contadino baratta 3 galline per un cane da guardia e cosi il lupo non si mangia nessuna gallina. La prima sera quante galline c'erano nel pollaio?

>>> Risposte & riflessioni

Walter Nicolussi
Detto X il numero da trovare e ragionando sul fatto che il numero di galline prima che il lupo le mangi dev'essere divisibile per 4 e che quelle mangiate dal lupo dev'essere intero, si arriva a: X = 5 + k16 con k>=0.
Resta però l'interrogativo se un lupo riesce a mangiare 5 o più galline a notte. Per cui direi che il numero cercato è 5.
PS: si potrebbe però dire anche che il numero iniziale di galline è 21 o 37 o 53 o ... e che il lupo la terza notte non mangia nemmeno una gallina perchè gli è venuta l'indigestione per quelle che ha mangiato le notti precedenti!

Giovanni Macchia
In realta', per come e' impostato il problema, vi sono infinite soluzioni a meno che il testo non vada interpretato in altro modo. Infatti, indichiamo con x il numero di galline che c'erano inizialmente nel pollaio. Dopo averne mangiata una, dai dati del problema si deduce che il numero di galline rimanenti deve essere un multiplo di 4 e pertanto possiamo scrivere

(1) x-1 = 4m

Dopo che il lupo ha mangiato 1/4 delle galline rimanenti, rimangono 3(x-1)/4 galline. Dopo averne comprate 5 si ha che il numero totale di galline e'

3(x-1)/4+5

Anche tale numero deve essere multiplo di 4, dai dati del problema. Si ha pertanto che

(2) 3(x-1)/4+5 = 4s

Se indichiamo p=3(x-1)/4 si ottiene

(3) p+5 = 4s

I p che soddisfano la (3) sono dati da

(4) p(t)=4t+3

dove t e' un intero. Sostituendo la (1) nel p(t) che compare nella (4) si ottiene

(5) 3m(t)=4t+3

che ammette le soluzioni per t = 3k e m=4k+1. Sostituendo m nella (1) si ottiene che sono possibili tutte le soluzioni con un numero di galline pari a

x = 5 + 16k

con k intero. Se consideriamo k=0, si parte con 5 galline, il contadino ne mangia una e ne rimane con 4 , il lupo ne mangia 1 (pari a 1/4) e ne rimangono 3. Aggiungendo 5 si hanno 8 galline . Il lupoo ne mangia 2 e ne rimangono 6, numero maggiore di 3. Analogamente si procede per 21, 37, etc. etc.
Pertanto, il problema ammette infinite soluzioni.

269. Il contadino e il recinto
di Mirko Segatello
Un contadino possiede un recinto con conigli e capre; ogni giorno il contadino deve decidere cosa mangiare. Se ci sono più conigli che capre mangia 1/3 dei conigli se ci sono più capre che conigli mangia 1/5 delle capre. Dopo 5 giorni però si accorge che il numero delle capre e dei conigli rimasti nel recinto sono uguali ed esclamò: "accidenti se mangiassi altri 2 conigli il numero delle capre sarebbe esattamente 1/4 dei conigli".
Quante capre e quanti conigli c'erano nel recinto all'inizio?

>>> Risposte & riflessioni

268. Le clessidre
di Mirko Segatello
Si dispone di una clessidra da 7 minuti e una da 13 minuti e si vuole misurare un tempo di 11 minuti; come si può fare con il numero minimo di passaggi?

>>> Risposte & riflessioni

267. Ordine lessico-grafico
di Eugenio
Ho trovato il modo di poter generare in ordine lessico-grafico liste lunghe L di N elementi senza ripetizioni; ma non riesco a trovare il modo di come conoscendo una lista possa risalire al suo posto d'ordine.
Non so se sono stato chiaro, forse un esempio è più esplicativo:
N=6
L=3
elementi {1,2,3,4,5,6}
Posto - Lista
1)...........{1,2,3}
2)...........{1,2,4}
3)...........{1,2,5}
4)........... {1,2,6}
5)...........{1,3,4}
6)...........{1,3,5}
7)...........{1,3,6}
8)...........{2,3,4}
9)...........{2,3,5}
10)...........{2,3,6}
...
15)...........{4,5,6}

Es: data La lista   {1,3,5}  come posso determinare il  valore "6"  che è il posto di generazione lessico grafico?

>>> Risposte & riflessioni

Un particolare ringraziamento a Paolo Hägler per la risposta inviata.

Paolo Hägler
Innanzitutto la sua lista va corretta e diventa:
 1 {1,2,3}
 2 {1,2,4}
 3 {1,2,5}
 4 {1,2,6}
 5 {1,3,4}
 6 {1,3,5}
 7 {1,3,6}
 8 {1,4,5}
 9 {1,4,6}
10 {1,5,6}
11 {2,3,4}
12 {2,3,5}
13 {2,3,6}
14 {2,4,5}
15 {2,4,6}
16 {2,5,6}
17 {3,4,5}
18 {3,4,6}
19 {3,5,6}
20 {4,5,6}

In effetti il coefficiente binomiale 6 su 3 (6!/((6-3)!3!)) fa 20. Ora passiamo al programma da lui richiesto, quello che all'elemento T (insieme di 3 numero da 1 a 6) della lista associa il numero in ordine lessicografico.

pos=1 (variabile che indica la posizione dell'elemento T alla fine dell'algoritmo)
j=1 (variabile che indica quale numero dell'elemento T stiamo seguendo)
For i = 1 to 6 (passiamo in rassegna tutti i 6 numeri che presi 3 a 3 formano gli elementi)
If i non elemento di T then
if j<=3 then
pos=pos+(6-i)!/((3-j)!*((6-i)-(3-j))!)
end if
else
j=j+1
end if
next

266. Le 100 mattonelle (variante fantasy)
di Ariman

Questo gioco è una variante del: 15. Il gioco delle 100 caselle inviato e risolto da Gianvittorio Righi. Lo pubblico ugualmente perché la presentazione è molto "intrigante".

Sei in un castello maledetto, hai superato tutte le prove che il malvagio Azaghal ti ha posto.
Tra te e l'uscita c'è soltanto una sala senza colonne.
Il mago ti appare al centro della sala e ti solleva da terra.
Vedi che il pavimento è formato da mattonelle quadrate, e che sono 100, disposte 10 x 10, a quadrato.
Azaghal ti pone l'ultima sfida. Per uscire dalla sala devi passare sopra tutte le mattonelle.
Appena passi su una mattonella questa sprofonda nell'abisso.
Stai per dirigerti verso la prima ma lui ti ferma.
Non puoi passare da una mattonella a quella vicina. Devi seguire queste tre regole:
1) Puoi iniziare e terminare il tuo percorso in una qualunque delle mattonelle, ma devi toccarle tutte.
2) Quando ti sposti in orizzontale e verticale devi saltare due mattonelle.
3) Quando ti sposti in diagonale devi saltare una mattonella.
Detto ciò il mago ti lascia con il suo ghigno malvagio stampato sul volto.

>>> Risposte & riflessioni

Questa è solo una delle tante (quante?) possibili soluzioni.

01 50 29 02 51 30 03 52 31 04
39 67 13 40 68 14 41 69 15 42
60 87 78 61 21 79 62 96 80 53
12 49 28 93 24 27 92 73 32 05
38 66 20 88 63 95 22 70 16 43
59 86 77 26 91 72 25 97 81 54
11 48 100 94 23 99 83 74 33 06
37 65 19 89 64 18 90 71 17 44
58 85 76 57 84 75 56 98 82 55
10 47 36 09 46 35 08 45 34 07

265. Chi vuol esser miliardario?
di Giorgio Dendi
Il programma di Scotti è tra quelli che preferisco, anche se raramente riesco a vedere anche una parte soltanto della trasmissione. Purtroppo anche pochi giorni fa ho potuto confermare i miei sospetti: la matematica è una cosa difficile, difficilissima, in quanto bisogna ragionare.
Questi i fatti: al concorrente dopo alcune domande viene posto un quesito che secondo me è il più banale che possa essere.
"Facendo la differenza tra un qualunque numero di due cifre e quello con le cifre invertite, il risultato è sempre divisibile per... 5? 7? 9? 11?"
Il concorrente era già avanti con la sua prestazione, quindi aveva già risposto correttamente ad altre domande, quindi sapeva... che ne so? quale era il primo segno dello zodiaco, come si scriveva Shakespeare, quale era la capitale della Mongolia, quale scultore era famoso per i colli lunghi, a quale famiglia apparteneva il bradipo, o cose simili.
Non voglio ora dire che siccome io e chi mi sta leggendo su queste pagine siamo appassionati di matematica, siamo per forza intelligenti e gli altri idioti, assolutamente, ma vorrei dire che la soluzione del quesito matematico è alla portata di tutti, proprio di tutti, e non necessità di conoscenze che invece sono indispensabili per rispondere a quiz di altro argomento.
Il concorrente infatti ha preso un numero di due cifre, mi sembra 25 e ha fatto la differenza con 52, e si è accorto che era divisibile, fra i numeri proposti, soltanto per 9.
Era l'unico dei quesiti proposti che andava risolto con un paio (un paio, non di più) di calcoli, ed era risolvibile da chiunque (il tempo a disposizione, fra l'altro, è quasi illimitato).
Perchè allora è stato messo da chi compila le domande fra i quesiti difficili? Non so se capita anche a voi, ma a me spesso succede che quando faccio qualche domandina matematica o pseudo matematica anche semplice ai miei amici o conoscenti occasionali, questi mi rispondono dicendo che la matematica non è per loro e cose simili, e magari il problema era quello del 135, nel quale bisognava girare il foglio (è qui nel Forum, ti ricordi?) o una cosetta divertente che però a causa del rigetto iniziale di qualcuno non posso proporre. Capita anche a te?

>>> Risposte & riflessioni

Riporto qui la risposta (con dimostrazione) alla domandina e di seguito metto in cornice la discussione del Forum sulla domanda più impegnativa e profonda di Giorgio Dendi.

Yirdic
Scriviamo

10x+y-(10y+x)=n -> 9x-9y=n

n deve quindi essere divisibile per 9 (meno di un minuto).

264. L'orologio
di Utervis
E' da un po' di tempo che ci chiediamo come mai se in un orologio si collegano con delle linee i punti sulla circonferenza corrispondenti alle seguenti coppie di ore:

12 - 5
1 - 8
2 - 10
3 - 11

i quattro segmenti si incontrano tutti in un unico punto.

N.d.R. Questa "foto" è stata fatta con lo scanner l'11 settembre 2002!
Erano le 3 di notte o le 3 di giorno?

Qualcuno sa qualcosa su questo problema e sul problema generale di determinare le intersezioni multiple fra le diagonali nei poligoni regolari?

>>> Risposte & riflessioni

Enrico Delfini
Consideriamo le corde 12-5 e 1-8; esse sono simmetriche rispetto all'asse 12,30-6,30 (il fatto che sia un diametro è ininfluente); ne deriva che il loro punto di intersezione deve trovarsi su tale asse di simmetria.
Anche le due corde corte ( 11-3 e 10-2) sono simmetriche rispetto allo stesso asse, o meglio formano figure simmetriche speculari rispetto ad esso: ne deriva che anche il loro punto di intersezione deve stare sull'asse 12,30-6,30.
Passiamo a considerare l'asse 2,30-10,30. le due coppie di corde (le due lunghe e le due corte) delimitano figure simmetriche/speculari anche rispetto a questo secondo asse. Per cui i punti di intersezione delle due coppie di corde devono giacere sulla stessa linea.
Ora, se devono giacere contemporaneamemnte su due linee, lo spazio a disposizione si riduce...
sinceramente non so se questa dimostrazione è corretta, però mi sembra carina, tanto per cominciare.

Sprmnt21
La concorrenza delle corde 1-8, 12-5, 3-11, 2-10 puo' essere provata procedendo nel seguente modo.
Consideriamo prima le due corde 12-5 e 1-8 e sia 0 il punto comune. L'angolo <12-1-8 e' di 60°. Infatti e' la meta' dell'angolo al centro che insiste sull'arco 8-12 cioe' 360°/3=120°. Analogamente si deduce che l'angolo <5-12-1=60°. Pertanto il triangolo, avendo 2 (e quindi anche il terzo)angoli di 60° 12-1-0 e' equilatero. In particolare si ha che 12-1=1-0. Essendo 1-2=12-1, si ha che 1-0=1-2. Consideriamo ora il triangolo 1-2-8, poiche' 2-8 e' un diametro <8-1-2=90°, percio' risulta che <1-0-2=<1-2-0=45°. L'angolo <1-8-2=15° in quanto meta' dell'angolo al centro corrispondente ad un'ora cioe' 360°/12=30°. Da questo si ha che <0-2-8= <1-0-2 - <0-8-2=45°-15°=30°. Questo implica direttamente che se prolunghiamo il segmento 2-0 dalla parte di 0 si passa per 10, infatti l'angolo <8-2-10=30°. Analogamente si puo' ragionare per la corda 11-3, oppure considerare la simmetria della figura rispetto alla bisettrice di <12-0-1.

Francesco Veneziano
Il problema di Utervis sulle intersezioni multiple delle diagonali di un poligono regolare mi ha interessato molto, quindi dopo qualche giorno di infruttuosi tentativi ho fatto una ricerca ed ho scoperto che questo è un problema "famoso" che circola da quasi un secolo tra i matematici ed è stato risolto correttamente solo nel 1995 (una soluzione precedente era sbagliata).
La dimostrazione si può reperire andando al sito http://arxiv.org/list/math/9508 e scaricando l'articolo 9508209 dei signori Poonen e Rubinstein. Purtroppo la dimostrazione, che si segue abbastanza facilmente, non è illuminante perchè rientra tra quelle (come la dimostrazione del teorema dei 4 colori) in cui il computer elabora una gran quantità di casi, e poi rimane da dimostrare solo che ogni configurazione si può ricondurre a quelle elaborate dal computer.
A titolo di curiosità allego il risultato finale; am(n) indica il numero di intersezioni di m diagonali all'interno di un n-agono regolare; dk(n) vale 1 se n è multiplo di k, e 0 altrimenti.
Dal conteggio è escluso il centro dei poligoni con un numero pari di lati. Si nota che se il numero dei lati è dispari non vi sono intersezioni multiple, e non si possono intersecare nello stesso punto più di 7 diagonali (escludendo sempre il centro dei poligoni con un numero pari di lati).

263. Il rettangolo antimagico
di Giorgio Dendi
Disegno una griglia di 3 quadratini di altezza e 4 di larghezza. Trovo già scritto nelle caselle della prima riga 1 1 1 2, e nelle prime tre della seconda 1 2 4.

Bisogna riempire tutte le cinque caselle vuote di questo rettangolo antimagico, cioè tale che le somme dei numeri di ogni linea o colonna sono sempre diverse fra loro e sempre minori o uguali a 9. Inoltre il rettangolo contiene soltanto i numeri 1, 2, e 4.
Questo problema è stato assegnato ai campionati di Parigi dell'anno scorso. Vediamo la soluzione proposta dal comitato organizzatore. Siccome ogni colonna o riga avrà come minimo totale uguale a 3, e non si deve superare 9 come totale, ogni valore tra 3 e 9 dovrà comparire in una riga o colonna come totale. Il totale di 3 si può ottenere solo nella prima colonna, quindi il primo valore della terza riga sarà 1. Cerco la colonna o riga che darà totale uguale a 4: sarà la seconda o la quarta colonna: se fosse la quarta, devo scrivere in essa 2-1-1. In tal caso la seconda riga da per totale 8 e siccome la prima riga da 5, per la seconda colonna mi rimane solo la combinazione 1-2-4 con totale 7, ma ciò mi impedisce di completare il quadro. Quindi è la seconda colonna che da per totale 4, con la combinazione 1-2-1. Ormai al quadro mancano pochi valori e si trova quasi subito.
Il problema è facilino, ma io ho trovato un procedimento che mi sembra migliore. Buon lavoro!

>>> Risposte & riflessioni

262. Indovinello delle infinite stanze
di Giulia
C'è un albergo con infinite stanze, l'albergatore non sa quali e quante stanze sono occupate. Ad un certo punto arriva una comitiva di 30 persone che chiedono se c'è posto. L'albergatore logicamente risponde di si ma come fa l'albergatore a trovare le 30 stanze?
Se si presentasse una comitiva di infinite persone come si dovrebbe comportare l'albergatore?

>>> Risposte & riflessioni

ap
Se ne arrivano 30, fa spostare tutti avanti di 30 stanze e li mette ai primi posti, così nessuno deve fare troppa strada.
Se ne arrivano infiniti... fa spostare tutti dalla stanza n alla stanza 2n, così si liberano tutte le stanze con i numeri dispari (a parte il 13 che l'albergatore ha saltato perché è superstizioso) ^__^

261. Matrix
di Hal8999
Questo è un problema carino che mi ha proposto una volta mio zio, non so se sia già presente sul sito:

Sia data una matrice bidimensionale e la si riempia per righe inserendo in ogni casella l'intero positivo (0 incluso) più basso che non sia già presente sulla stessa riga o sulla stessa colonna. Dati i e j siete in grado di determinare m(i,j)?

A titolo di esempio riporto l'inizio delle prime 2 righe (giacché la matrice è per sua natura infinita):

012345.....
103254.....

Chi non ci riuscisse può consolarsi con questo: qual è il numero più grande che si può scrivere con 3 cifre?

>>> Risposte & riflessioni

In sintesi la risposta è:
m(i,j)= i XOR j
Sprmnt21, oltre alla risposta esatta, simpatica ed informale che inserisco qui sotto, mi ha inviato una dimostrazione formalizzata della risposta.

Sprmnt21
Ci provo io.
Per adesso non formalizzo la cosa, provo a dare solo una idea di come credo che funzioni il gioco.
Per seguire le osservazioni, si scrivano un bel po' di numeri in forma di matrice seguendo le definizioni date.

I) Si osservi innanzitutto che la diagonale principale della matrice e' tutta zero, cioe' gli elementi m(i,i)=0.

II) Si osservi che ogni sottomatrice principale (che ha cioe' la stessa diagonale della matrice completa) di ordine 2^k (con k intero) ha una doppia simmetria, cioe' e' simmetrica rispetto alle due diagonali.

In attesa di trovare una terminologia piu' appropriata, battezziamo un'altra caretteristica della matrice dicendo che ha una simmetria a blocchi ricorsiva.
Per spiegare il senso di questa curiosa definizione, si osservi che la matrice [[0,1];[1,0]] con il primo elemento in posizione (0,0) si ripete con il primo elemento in posizione (2,2); la matrice [[2,3];[3,2]] con primo elemento in posizione (0,2) si ripete con primo elemento in posizione (2,0).
La matrice composta da questi 4 blocchetti si ripete partendo dalla posizione (4,4).

III) Si noti infine che ogni sottomatrice principale "traslata" lungo le righe o le colonne di un numero di posti multiplo del suo ordine si ripete con gli elementi aumentati del numero di posti traslati.
Ad esempio traslando la sottomatrice principale di ordine 4 di 3*4 posti diventa [[12,13,14,15]; ...;[15,14,13,12]].

A questo punto dovremmo aver tutto per procedere a determinare, ad esempio, il valore di m(19,11).

Poiche' la potenza di 2 immediatamente inferiore a 19 e' 2^4=16, per la III) abbiamo che m(19,11)=16+m(3,11). Dobbiamo quindi calcolare m(3,11), ma sempre per III) m(3,11)=8+m(3,3): Per la I) m(3,39)=0. Percio' m(19,11)=24.

Un'altro giro per trovare quanto vale m(23,8). Per comodita' anziche' m(x,y) scrivo solo (x,y)

(23,8)=16+(7,8)=16+8+(7,0)=24+4+(3,0)=28+2+(1,0)=30+1+(0,0)=31.
In effetti in questo caso potevamo subito concludere che (7,0)=0.

Ora sono quasi certo che questa procedura, con un po' di pazienza, puo' essere compattata in una formula esplicita con combinazioni di potenze del due.
Ma ci vuole un po' di pazienza.
Mi aspetto invece che Hal ci dia una mano.

...

Ma forse e' vero che lavare i denti fa bene.

Ecco cosa ho trovato nel tubetto del dentifricio:

m(i,j)= i XOR j,

il tutto in base 2.

Che cosa significa XOR?

Per come l'intendo io XOR e' un'operazione binaria (che si applica a due argomenti cioe', tipo l'AND e l'OR) definita cosi:


1 XOR 0 = 1;
1 XOR 1 = 0;
0 XOR 0 = 0;
0 XOR 1 = 1;

cioe' l'operazione da' 1 solo per valori diversi e 0 per valori uguali degli argomenti.

Lo XOR di due stringhe binarie si fa elemento ad a lemento partendo da DESTRA (aggiungendo degli zeri quando necessario) applicando la regola precedente.

Ad esempio: 10001 XOR 101 e' uguale a 10001 XOR 00101 = 10100.

La soluzione del gioco richiede di trasformare le due coordinate (i,j) in binario e poi fare lo XOR delle stringhe ottenendo una terzxa stringa che trasformata in decimale da' il valore contenuto nella casella m(i,j).

Provare per credere.

Hal8999
Beh per come ha ragionato sprnmt21 in effetti la connesione con l'EXOR è meno intuitiva. Io ho ragionato così: la matrice oltre che simmetrica nel senso classico (m(i,j) = m(j,i)) è simmetrica a blocchi di 2 per cui se consideriamo i primi 4 elementi abbiamo

01
10

se consideriamo i quattro a destra abbiamo

23
32

e infine notiamo che la simmetria si mantiene a blocchi di 2^k

01 23
10 32

23 01
32 10

Ora il nostro problema è determinare m(i,j): assumiamo anzitutto i>j (poiché la matrice è simmetrica ciò non è restrittivo) e chiamiamo M l'intero superiore del logaritmo in base 2 di i. Possiamo considerare ora la nostra matrice come formata da 4 blocchi di dimensione 2^M

1 2
2 1

m(i,j) si troverà nel blocco 2: dunque togliamo M a i e ripetiamo la procedura ricorsivamente considerando di volta in volta la potenza di 2 inferiore e togliendola a i e/o j se ivi presente. Forse adesso appare più chiara l'analogia con l'EXOR poichè il problema ha natura ricorsiva e la sua essenza è rappresentata dal blocco fondamentale

01
10

nel quale abbiamo 1 per i != j e 0 altrimenti il che è proprio ciò che fa l'EXOR per numeri a una cifra...estendete il concetto a n cifre e avrete la soluzione del problema...spero di non essere stato troppo criptico...by the way il numero + grande che si può scrivere con 3 cifre è
9^(9^9)= 1,9662705047555291361807590852691e77

...

Vorrei precisare (visto che non sono stato molto chiaro) che il numero m(i,j) si trova come sommatoria: gli addendi saranno potenze di 2 a partire da 2^M e se ne aggiungerà uno ogni volta che la relativa potenza di 2 è presente in i (che si aggiorna di volta in volta) o in j (idem) MA NON IN ENTRAMBI. In questo caso infatti invece che muoverci in basso e poi a destra possiamo restare sul primo blocco del quadrato

0 2^M
2^M 0

Le potenze di 2 si aggiungono perché il blocco 2^M ha come elemento (0,0) 2^M come si vede scrivendo alcuni numeri della matrice...quindi riassumendo si divide ogni volta la matrice in 4 blocchi e si sceglie il blocco nel quale è m(i,j), si aggiunge la relativa potenza di 2 alla sommatoria e si ripete il procedimento aggiornando gli indici i e j. Poiché la sommatoria contiene solo le potenze di 2 presenti in i O (esclusivo) j ecco realizzato l'EXOR...ammetto che l'essere un ingegnere informatico mi ha facilitato nel formalizzare il tutto...

Sito Web realizzato da Gianfranco Bo