Abbiamo una torta circolare, con n ciliegine disposte regolarmente intorno ai bordi e ad ognuna di esse assegniamo un numero da 1 a n, mai due volte lo stesso numero. Diciamo che due ciliegie A e B sono a distanza m, e scriviamo (A, B)=m, se partendo dalla ciliegia A e procedendo in senso orario l'emmesima ciliegia incontrata è B; quale immediato corollario si ha che (B, A)=n-m.
Esempio. Sia n=6 e le ciliegie numerate in questo modo:
1 5 3 4 6 2
allora le ciliegie 5 e 2 sono a distanza 4, perché 2 è la quarta ciliegia che si trova dopo la 5. Invece le ciliegie 2 e 5 sono a distanza due, perché partendo da 2 prima troviamo 1 e subito dopo 5, (5, 2)=4, (2, 5)=2.
Un taglio della torta si può fare solo se passa attraverso due ciliegie di parità opposta, cioè una deve avere numero pari e l'altra dispari. Con riferimento all'esempio sopra, vediamo quanti tagli si possono fare secondo le distanze delle coppie di ciliegie attraverso cui passa il coltello.
Tagli a distanza 1 = {(3, 4), (2, 1)}
due coppie, dunque sono possibili 2 tagli;
tagli a distanza 2 = {(5, 4), (3, 6), (6, 1), (2, 5)}
= 4 tagli
tagli a distanza 3 = {(1, 4), (5, 6), (3, 2), (4, 1), (6, 5), (2, 3)}
= 6 tagli
tagli a distanza 4 = {(1, 6), (5, 2), (4, 5), (6, 3)}
= 4 tagli
tagli a distanza 5 = {(1, 2), (4, 3)}
= 2 tagli
Abbiamo una equipartizione della torta se il numero dei tagli è uguale per tutte le distanze, cioè se:
numero di tagli a distanza 1 = numero di tagli a distanza 2 = numero di tagli a distanza 3 = ...
Problema 1. Assegnare i numeri da 1 a 15 in modo da avere una equipartizione di una torta con 15 ciliegine.
Problema 2. Una equipartizione è possibile solo per certi valori di n, quali? Dimostrarlo.
Il taglio della torta
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
-
Sancho Panza
- Livello 4
- Messaggi: 151
- Iscritto il: gio ott 12, 2006 9:01 pm
sarà colpa del sole preso sul greto del Magra, ma non riesco a capire di quale tipo di tagli si parla.
Un taglio significa che la torta rimane divisa in due pezzi? o il taglio stesso non va da parte a parte, ma si limita a essere un "raggio" della torre "cerchio" ? o addirittura "un taglio" equivale ai "due Tagli" che creano una fetta? e come la mettiamo con le corde? (conosco persone che non tagliano mai una torta a fette "standard" ma a "corde progressive"....
Passare "attraverso due ciliegie di parità opposta" significa "tra le due ciliegie" o proprio che il taglio divide in due le piccole drupe ? (in questo caso il problema non vale, perchè tutti sanno che se si cerca di fare ciò, l'entropia della torta subisce una accelerazione che la destruttura rapidamente....
Un taglio significa che la torta rimane divisa in due pezzi? o il taglio stesso non va da parte a parte, ma si limita a essere un "raggio" della torre "cerchio" ? o addirittura "un taglio" equivale ai "due Tagli" che creano una fetta? e come la mettiamo con le corde? (conosco persone che non tagliano mai una torta a fette "standard" ma a "corde progressive"....
Passare "attraverso due ciliegie di parità opposta" significa "tra le due ciliegie" o proprio che il taglio divide in due le piccole drupe ? (in questo caso il problema non vale, perchè tutti sanno che se si cerca di fare ciò, l'entropia della torta subisce una accelerazione che la destruttura rapidamente....
Enrico
-
mathmum
- Livello 5
- Messaggi: 337
- Iscritto il: sab nov 19, 2005 5:39 pm
- Località: World (Wide Web) - IT
Guarda un po' qui...
http://en.wikipedia.org/wiki/Fair_division
oppure nella Bibbia:
http://mathworld.wolfram.com/CakeCutting.html
in italiano:
http://www.economia.unige.it/04/diem/ne ... .4.doc.doc
ciao
http://en.wikipedia.org/wiki/Fair_division
oppure nella Bibbia:
http://mathworld.wolfram.com/CakeCutting.html
in italiano:
http://www.economia.unige.it/04/diem/ne ... .4.doc.doc
ciao
mathmum
...la vita è complessa: ha componenti reali ed immaginarie...
...la vita è complessa: ha componenti reali ed immaginarie...
Immagino che delfo52 scherzi, ma nel problema la parola "taglio" indica una coppia di numeri: uno dev'essere dispari e l'altro pari.
@Jumpy94: se non trovi un'equipartizione della torta con 5 ciliegine i caso sono due, o non c'è o è impossibile che ci sia, se capisci la differenza allora sei a metà strada. Insisti.
@Jumpy94: se non trovi un'equipartizione della torta con 5 ciliegine i caso sono due, o non c'è o è impossibile che ci sia, se capisci la differenza allora sei a metà strada. Insisti.
Complicato.
A intuito, direi che dovrebbe essere possibile per n=3,7,15,31,63,.......ed ammettendo che fosse vero, la spiegazione sarebbe molto debole, perché si basa sul fatto che mi è riuscito solo per n=3,7
1,3,2
1,6,2,5,3,7,4
A intuito, direi che dovrebbe essere possibile per n=3,7,15,31,63,.......ed ammettendo che fosse vero, la spiegazione sarebbe molto debole, perché si basa sul fatto che mi è riuscito solo per n=3,7
1,3,2
1,6,2,5,3,7,4
_________________
$\text { }$ciao
ciao
E' la somma che fa il totale (Totò)
$\text { }$ciao
E' la somma che fa il totale (Totò)
per n=3,7,15 vale la mia ipotesi iniziale e se questa più quella di Pasquale sono esatte (la mia nelle dovute restrizioni) vale anche per i restanti 31,63,.....Credo che a breve posterò come ho ricavato quella formula per vedere se qualcuno la può modificare laddove forse sono stato sbadato.
Una vita senza ricerca
non è degna di essere vissuta.
Socrate
non è degna di essere vissuta.
Socrate
Per ora dico che per $n$ pari non si possono avere equipartizioni.
Infatti abbiamo $\frac{n^{2}}{2}$ possibili coppie che rispettano la condizione che i loro elementi siano uno pari e l'altro dispari. Premettendo che ad ogni coppia corrisponde solo una distanza, il numero di tagli sono $n-1$ (questo perché sulla circonferenza ci sarà sempre una coppia di numeri adiacenti pari e dispari), così da avere ad ogni taglio $\frac{n^2}{2(n-1)}$ distanze uguali tra di loro, in numero intero. Dimostro il contrario.
Possiamo considerare $\frac{n^2}{2(n-1)}=k$, con $k$ intero positivo, ed in particolare (scomponendo) $(n+1)+\left(\frac{1}{n-1}\right)=2k$. Si vede in maniera molto evidente come il secondo termine del primo membro non può essere intero, il ché dimostra che per n pari non esiste alcuna equipartizione.
SE&O
Ciao.
____________________________________________________________________
Ho problemi con le dimensioni dei caratteri, per cui dico che $n^2$ è la seconda potenza di $n$.
Infatti abbiamo $\frac{n^{2}}{2}$ possibili coppie che rispettano la condizione che i loro elementi siano uno pari e l'altro dispari. Premettendo che ad ogni coppia corrisponde solo una distanza, il numero di tagli sono $n-1$ (questo perché sulla circonferenza ci sarà sempre una coppia di numeri adiacenti pari e dispari), così da avere ad ogni taglio $\frac{n^2}{2(n-1)}$ distanze uguali tra di loro, in numero intero. Dimostro il contrario.
Possiamo considerare $\frac{n^2}{2(n-1)}=k$, con $k$ intero positivo, ed in particolare (scomponendo) $(n+1)+\left(\frac{1}{n-1}\right)=2k$. Si vede in maniera molto evidente come il secondo termine del primo membro non può essere intero, il ché dimostra che per n pari non esiste alcuna equipartizione.
SE&O
Ciao.
____________________________________________________________________
Ho problemi con le dimensioni dei caratteri, per cui dico che $n^2$ è la seconda potenza di $n$.
Una vita senza ricerca
non è degna di essere vissuta.
Socrate
non è degna di essere vissuta.
Socrate
Giustamente Jumpy94 fa vedere che n dev'essere dispari, ma di che tipo? Visto che si sta prendendo una strada sbagliata lo dico io, più sotto, in fondo, preceduto da un avviso, tanto manca sempre la dimostrazione, oppure non leggete l'ultima frase. Il mio consiglio è di fare delle prove con n=3, 4, 5, 6 e 7, osservando bene cosa succede.
Data una soluzione con n=7 ciliegine, per esempio:
1 2 4 5 6 3 7
costruiamo la tabella delle distanze in questo modo: numeriamo le righe r con i numeri dispari (in rosso), le colonne c con i numeri pari (in rosso) e nella posizione (r, c) scriviamo la distanza (r, c). Così all'incrocio della riga 1 con la colonna 4 scriveremo 2, perché la distanza tra la ciliegia 1 e la ciliegia 4 è di due passi, (1, 4)=2.
2 4 6
1 2 4 | 1
3 4 6 | 3
5 6 1 | 5
2 3 5 | 7
Gli elementi della riga 3 son contenuti nella colonna 4, gli elementi della riga 5 son contenuti nella colonna 6 e gli elementi della riga 7 son contenuti nella colonna 2; la riga 1 non è contenuta in nessuna colonna perciò la cancelliamo; inoltre scambiamo tra loro le righe 3 e 5, ottenendo:
2 4 6
5 6 1 | 5
3 4 6 | 3
2 3 5 | 7
Una tabella simmetrica rispetto alla diagonale (quella contraria)! Lo stesso succede con n=11. Invece dalla soluzione di Sancho Panza ricaviamo:
02 04 06 08 10 12 14
03 04 05 07 08 11 13 | 01
02 03 04 06 07 10 12 | 03
01 02 03 05 06 09 11 | 05
12 13 14 01 02 05 07 | 07
09 10 11 13 14 02 04 | 09
08 09 10 12 13 01 03 | 11
06 07 08 10 11 14 01 | 13
04 05 06 08 09 12 14 | 15
i cui elementi in comune formano la tabella simmetrica 5x5:
02 06 08 10 12
12 14 01 02 05 | 07
09 11 13 14 02 | 09
08 10 12 13 01 | 11
06 08 10 11 14 | 13
04 06 08 09 12 | 15
soluzione parziale in arrivo...
soluzione parziale in arrivo...
soluzione parziale in arrivo...
soluzione parziale in arrivo...
soluzione parziale in arrivo...
Immagino ci sia un rapporto tra il lato della tabella simmetrica e n, tra 5 e 15, tra 7 e 7, e tra 11 e 11, forse tramite essi si potrebbe dimostrare che esiste sempre un'equipartizione, ma qui ci vuole qualcuno più bravo di me; io finora so solo che n=4k+3 è condizione necessaria, per la sufficienza è tutto da vedere.
Data una soluzione con n=7 ciliegine, per esempio:
1 2 4 5 6 3 7
costruiamo la tabella delle distanze in questo modo: numeriamo le righe r con i numeri dispari (in rosso), le colonne c con i numeri pari (in rosso) e nella posizione (r, c) scriviamo la distanza (r, c). Così all'incrocio della riga 1 con la colonna 4 scriveremo 2, perché la distanza tra la ciliegia 1 e la ciliegia 4 è di due passi, (1, 4)=2.
2 4 6
1 2 4 | 1
3 4 6 | 3
5 6 1 | 5
2 3 5 | 7
Gli elementi della riga 3 son contenuti nella colonna 4, gli elementi della riga 5 son contenuti nella colonna 6 e gli elementi della riga 7 son contenuti nella colonna 2; la riga 1 non è contenuta in nessuna colonna perciò la cancelliamo; inoltre scambiamo tra loro le righe 3 e 5, ottenendo:
2 4 6
5 6 1 | 5
3 4 6 | 3
2 3 5 | 7
Una tabella simmetrica rispetto alla diagonale (quella contraria)! Lo stesso succede con n=11. Invece dalla soluzione di Sancho Panza ricaviamo:
02 04 06 08 10 12 14
03 04 05 07 08 11 13 | 01
02 03 04 06 07 10 12 | 03
01 02 03 05 06 09 11 | 05
12 13 14 01 02 05 07 | 07
09 10 11 13 14 02 04 | 09
08 09 10 12 13 01 03 | 11
06 07 08 10 11 14 01 | 13
04 05 06 08 09 12 14 | 15
i cui elementi in comune formano la tabella simmetrica 5x5:
02 06 08 10 12
12 14 01 02 05 | 07
09 11 13 14 02 | 09
08 10 12 13 01 | 11
06 08 10 11 14 | 13
04 06 08 09 12 | 15
soluzione parziale in arrivo...
soluzione parziale in arrivo...
soluzione parziale in arrivo...
soluzione parziale in arrivo...
soluzione parziale in arrivo...
Immagino ci sia un rapporto tra il lato della tabella simmetrica e n, tra 5 e 15, tra 7 e 7, e tra 11 e 11, forse tramite essi si potrebbe dimostrare che esiste sempre un'equipartizione, ma qui ci vuole qualcuno più bravo di me; io finora so solo che n=4k+3 è condizione necessaria, per la sufficienza è tutto da vedere.
-
Sancho Panza
- Livello 4
- Messaggi: 151
- Iscritto il: gio ott 12, 2006 9:01 pm
-
Sancho Panza
- Livello 4
- Messaggi: 151
- Iscritto il: gio ott 12, 2006 9:01 pm
In attesa di risolvere il problema, alcune soluzioni per alcuni valori di N:
Per n = 19
1, 3, 5, 7, 2, 4, 9, 11, 6, 13, 15, 8, 10, 12, 14, 17, 16, 19, 18
Per n = 23
1, 3, 5, 7, 9, 2, 11, 4, 13, 15, 6, 8, 17, 19, 10, 12, 21, 14, 23, 16, 18, 20, 22
Per n = 31
1, 3, 5, 7, 2, 9, 11, 4, 13, 15, 17, 6, 8, 19, 10, 12, 21, 14, 16, 18, 20, 23, 25, 27, 22, 29, 24, 31, 26, 28, 30
(Spero che siano corrette; le ho trovate con il computer senza verificarle)
Per Jumpy94:
potresti inserire la tua soluzione valida anche per N=31 e N=63
(quella di cui parli nel tuo primo intervento del 17 maggio)
Grazie
Per n = 19
1, 3, 5, 7, 2, 4, 9, 11, 6, 13, 15, 8, 10, 12, 14, 17, 16, 19, 18
Per n = 23
1, 3, 5, 7, 9, 2, 11, 4, 13, 15, 6, 8, 17, 19, 10, 12, 21, 14, 23, 16, 18, 20, 22
Per n = 31
1, 3, 5, 7, 2, 9, 11, 4, 13, 15, 17, 6, 8, 19, 10, 12, 21, 14, 16, 18, 20, 23, 25, 27, 22, 29, 24, 31, 26, 28, 30
(Spero che siano corrette; le ho trovate con il computer senza verificarle)
Per Jumpy94:
potresti inserire la tua soluzione valida anche per N=31 e N=63
(quella di cui parli nel tuo primo intervento del 17 maggio)
Grazie
Mi verrebbe difficile fare a mano le prove per n=63 (dato che non so creare programmi), per cui nell'intervento da te citato Sancho Panza mi riferivo alle previsioni del numero di tagli per equipartizione che per particolari n era per me (n+1)/2, formula ancora valida per tutte le prove fin ora fatte da voi. D'altronde è stata ottenuta similmente alla dimostrazione fatta da me poco tempo fa per i numeri pari. Vi prego non consideratemi come un vigliacco 
Una vita senza ricerca
non è degna di essere vissuta.
Socrate
non è degna di essere vissuta.
Socrate