Precedente :: Successivo |
Autore |
Messaggio |
Salmastro Dio minore
Registrato: 13/12/06 19:36 Messaggi: 883 Residenza: Casalmico
|
Inviato: 30 Dic 2009 23:53 Oggetto: Il gioco delle biglie di vetro |
|
|
ovvero, Das Glaskugelnspiel
Il piccolo Pierino Greco, che gli amici chiamano “pigreco”, durante le vacanze di Natale ha vinto un ragguardevole numero di biglie di vetro ed ora le vuole conservare.
Suo padre, un “sadico” prof. di matematica, gli impone di usare dei contenitori a tre settori che, messi uno sull’altro, formano una fila virtualmente infinita.
Le biglie vanno messe via seguendo tre semplici regole:
1. Ogni settore deve contenere un diverso numero di biglie;
2. Ogni riga deve avere lo stesso numero di biglie;
3. Il numero di biglie deve essere il minimo in ogni riga.
Giusto per fare un esempio, se le righe fossero due, si potrebbe fare così:
---------------
! 1 ! 3 ! 7 !
---------------
! 2 ! 4 ! 5 !
---------------
E se le righe fossero K ?
P.S.: l’importante è riempire tutti i settori, ché le biglie sono “virtualmente” infinite. |
|
Top |
|
|
Scrigno Semidio
Registrato: 26/07/09 04:32 Messaggi: 313
|
Inviato: 01 Gen 2010 19:15 Oggetto: |
|
|
Sal:
Quando dici che:
1. Ogni settore deve contenere un diverso numero di biglie;
intendi ogni settore della singola riga e non ogni settore di tutte le K righe. vero?
Per intenderci:
---------------
! 1 ! 3 ! 7 !
---------------
! 2 ! 4 ! 5 !
---------------
! 2 ! 3 ! 6 !
---------------
é una pila ben costruita? |
|
Top |
|
|
Salmastro Dio minore
Registrato: 13/12/06 19:36 Messaggi: 883 Residenza: Casalmico
|
Inviato: 02 Gen 2010 13:59 Oggetto: |
|
|
@ Scrigno:
ahinoi, ogni singolo settore (a qualsiasi riga appartenga) deve contenere un numero diverso di biglie |
|
Top |
|
|
Scrigno Semidio
Registrato: 26/07/09 04:32 Messaggi: 313
|
Inviato: 02 Gen 2010 16:28 Oggetto: |
|
|
Spero, Sal, di aver ben capito:
Ecco la mia soluzione
Citazione: | E visto che non potevo postare qualcosa senza fare nemmeno un errore:
ecco la prima correzione
La 14a riga, dove dice di partire dalla riga con meno biglie (2+2n) Ha bisogno non di una ma di due correzioni
La riga con primo settore = n e secondo = 2n è la riga Ennesima ed ha, logicamente PIù bigle delle precedenti.
La formula messa tra parentesi non è 2+2n ma, piuttosto, n+2n |
Il testo nell' immagine è gia raster e non mi andava di rifare tutto sorry. spero sia tutto chiaro comunque.
Per inciso; l' andamento del incremento deve essere Citazione: | questo che, tra l' altro, anche se si nota poco perchè hai utilizzato solo due righe, è identico a quello postato da te |
|
|
Top |
|
|
Jowex Eroe in grazia degli dei
Registrato: 15/04/06 14:20 Messaggi: 90
|
Inviato: 02 Gen 2010 19:44 Oggetto: |
|
|
Secondo me si può fare di meglio, ma ci sto ancora lavorando quindi non mi sbilancio! |
|
Top |
|
|
Scrigno Semidio
Registrato: 26/07/09 04:32 Messaggi: 313
|
Inviato: 03 Gen 2010 08:40 Oggetto: |
|
|
Jowex ha scritto: | Secondo me si può fare di meglio, ma ci sto ancora lavorando quindi non mi sbilancio! |
In che senso Jowex?
La soluzione non è esatta?
O forse una differente disposizione delle bigle affinchè se ne abbiano di meno? |
|
Top |
|
|
Salmastro Dio minore
Registrato: 13/12/06 19:36 Messaggi: 883 Residenza: Casalmico
|
Inviato: 03 Gen 2010 15:34 Oggetto: |
|
|
Scrigno ha scritto: | Jowex ha scritto: | Secondo me si può fare di meglio, ma ci sto ancora lavorando quindi non mi sbilancio! |
In che senso Jowex?
La soluzione non è esatta?
O forse una differente disposizione delle bigle affinchè se ne abbiano di meno? |
credo che Jowex voglia dire che sono state rispettate la regola 1) e la regola 2) e che sta lavorando (come me, d'altronde ) per verificare se è rispettata anche la regola 3) (quella del minimo) |
|
Top |
|
|
Jowex Eroe in grazia degli dei
Registrato: 15/04/06 14:20 Messaggi: 90
|
Inviato: 03 Gen 2010 16:03 Oggetto: |
|
|
Sì intendevo proprio ciò che ha scritto Salmastro, la soluzione è giusta ma non è quella che minimizza il numero di biglie usate per ogni riga |
|
Top |
|
|
Jowex Eroe in grazia degli dei
Registrato: 15/04/06 14:20 Messaggi: 90
|
Inviato: 03 Gen 2010 16:11 Oggetto: |
|
|
Un possibile procedimento:
Citazione: | Il numero minimo teorico di biglie per riga si puo' ottenere se si riescono a riempire tutte le celle usando soltanto i numeri da 1 a 3k, dove k è il numero di righe.
In questo caso il numero minimo teorico si ottiene dividendo per k la somma dei numeri da 1 a 3k:
R(k) = sum(i da 1 a 3k) / k = 3k(3k+1)/2k = 3(3k+1)/2 = (9k+3)/2 che vale se k è dispari.
Se k è pari, R deve essere approssimato all'unità successiva e R(k) = 3(3k+1)/2 + 1/2 = (9k+4)/2
Alcuni esempi: R(1)=6, R(2)=11, R(3)=15, R(4)=20, R(5)=24, R(6)=29, R(7)=33, R(8 )=38 ...
Nel caso di k pari, se chiamo T la somma dei numeri da 1 a 3k, e S la somma di tutti i numeri effettivamente usati, queste quantità differiscono di:
S(k)-T(k) = k*(9k+4)/2 - k*(9k+3)/2 = k/2
ovvero i numeri da utilizzare non sono tutti quelli da 1 a 3k, ma almeno uno va sostituito con un numero maggiore di 3k, in modo che la somma totale differisca di k/2.
Per es, se k=4, devo prendere i numeri da 1 a 3k=12 e sostituirne uno, per es. il 12 con il 14, oppure l'11 con il 13 (che equivale a saltare il numero di posto k/2 contando da 3k all'indietro)
Resta da verificare se esiste sempre una soluzione che permette di raggiungere questo risultato.
Ecco come si puo' fare se k è dispari:
- riempio la prima colonna con i numeri da 1 a k dall'alto al basso
- restano i numeri da k+1 a 2k (che metteremo nella seconda colonna) e quelli da 2k+1 a 3k (che metteremo nella terza colonna)
- prendo il più piccolo della terza colonna (2k+1) e il più grande della seconda (2k): la somma dà 4k+1, e per arrivare al totale per riga mancano 3(3k+1)/2 - (4k+1) = (k+1)/2, quindi possiamo mettere questi due numeri alla riga corrispondente (che è quella di mezzo).
- ora procediamo riempiendo tutta la terza colonna in sequenza dal numero appena inserito (2k+1) verso il basso, ripartendo dalla prima riga dopo avere raggiunto l'ultima
- restano solo i numeri della seconda colonna, che sono determinati in modo univoco perché la somma di ogni riga è stata determinata in partenza
Il procedimento porta sempre al risultato cercato perché la somma del primo e del terzo numero di ogni riga è diversa da quella delle altre righe.
Se k è pari, si procede allo stesso modo per riempire la prima colonna, ma la terza colonna viene riempita a partire dalla riga k/2+1, e quando si riparte dalla prima riga, il numero da inserire viene incrementato di 2 (invece di 1) . La seconda colonna è sempre determinata come nel caso di k dispari.
Per riepilogare:
R(k) = (9k+3)/2 se k dispari
R(k) = (9k+4)/2 se k pari
|
Dato un certo k, ho verificato che le soluzioni trovate con questo procedimento non sono le uniche esistenti.
Tuttavia il problema non è del tutto risolto, perché ho verificato che il procedimento funziona, ma non perché....
Una strada alternativa potrebbe essere quella di cercare di dimostrare che esiste sempre almeno una soluzione, senza dimostrare quale (dato che non è unica) |
|
Top |
|
|
Jowex Eroe in grazia degli dei
Registrato: 15/04/06 14:20 Messaggi: 90
|
Inviato: 03 Gen 2010 16:12 Oggetto: |
|
|
Alcuni esempi per k da 1 a 8:
Citazione: | k=1, R=6
1 2 3
k=2, R=11
1 3 7
2 4 5
k=3, R=15
1 5 9
2 6 7
3 4 8
k=4, R=20
1 7 12
2 5 13
3 8 9
4 6 10
k=5, R=24
1 9 14
2 7 15
3 10 11
4 8 12
5 6 13
k=6, R=29
1 11 17
2 9 18
3 7 19
4 12 13
5 10 14
6 8 15
k=7, R=33
1 13 19
2 11 20
3 9 21
4 14 15
5 12 16
6 10 17
7 8 18
k=8, R=38
1 15 22
2 13 23
3 11 24
4 9 25
5 16 17
6 14 18
7 12 19
8 10 20 |
|
|
Top |
|
|
Salmastro Dio minore
Registrato: 13/12/06 19:36 Messaggi: 883 Residenza: Casalmico
|
Inviato: 04 Gen 2010 13:12 Oggetto: |
|
|
Beh, direi che Jowex ha brillantemente risolto l’insidioso quesito, indicando la retta strada per l’inserimento delle biglie e proponendo, per i vari casi, una delle possibili soluzioni
Dico possibili in quanto, come lui stesso afferma, non è detto che la soluzione sia unica:
Citazione: | per esempio, nel caso di 7 righe, Jowex mostra:
1 13 19
2 11 20
3 9 21
4 14 15
5 12 16
6 10 17
7 8 18
Ed io trovo:
1 14 18
2 12 19
3 10 20
4 8 21
5 13 15
6 11 16
7 9 17
Sostanzialmente le due tabelle si somigliano assai: tutte hanno nella prima colonna i numeri da 1 a 7 (in generale da 1 a k, essendo k il numero delle righe), nella seconda quelli da 8 a 14 (da k+1 a 2k), nella terza i restanti, da 15 a 21 (da 2k+1 a 3k). In entrambe, a parte il naturale ordinamento progressivo nella prima colonna, si notano certe simmetrie: nella seconda colonna pari e dispari decrescenti (per Jowex prima i dispari, io metto prima i pari), mentre la terza è costruita ad “orologio”.
Onestamente non so se esistano soluzioni diverse da quelle in cui (opportunamente scambiando le biglie delle singole righe, nonché righe intere) il numero delle palline sia ripartito come negli esempi: in prima colonna i numeri “piccoli”, seconda con numeri “medi” e terza con quelli “grandi”
P.S.: alla disamina di Jowex, apprezzabile per completezza e rigore, posso solo aggiungere na piccola riflessione, distinguendo il numero delle righe, k, in pari e dispari, per cui k=2m, se pari e k=2m+1, se dispari. Nel prosieguo indicherò con S la somma di tutte le biglie, con R quelle contenute in una singola riga.
Per il caso dispari (vi risparmio i calcoli) si ha S=18m^2 + 21m +6; R=9m+6 (cfr. Jowex)
Dividendo il polinomio in m indicato con S per quello, sempre in m, detto R si ottiene che
S=R*(2m+1)=R*k….risultato ovvio! Ce l’aspettavamo e non poteva essere altrimenti!
Più interessante il caso k pari, ché bisogna “saltare” un numero!
In questo caso introduco S’=S+s, cioè una quantità data dalla somma dei primi 3k+1 numeri interi: quelli che useremo più il “saltato”. Omettendo, ancora una volta i calcoli brutali, otteniamo:
S’=18m^2 +9m +1; R= 9m +2 (cfr. Jowex). Dividendo S’ per R otteniamo:
S’= 2m*(9m +2) + (5m +1) = R*k + (5m +1)
La quantità (5m +1) è evidentemente il numero da omettere (quello indicato con s minuscolo) e sarà sempre quella, se vogliamo minimizzare il totale delle palline utilizzate!
Ad esempio, nel caso k=8, si ha m=4 e (5m+1)=21, che è proprio il numero non usato da Jowex nelle sua tabella:
1 15 22
2 13 23
3 11 24
4 9 25
5 16 17
6 14 18
7 12 19
8 10 20
|
...@ Jowex: |
|
Top |
|
|
|
|
Non puoi inserire nuovi argomenti Non puoi rispondere a nessun argomento Non puoi modificare i tuoi messaggi Non puoi cancellare i tuoi messaggi Non puoi votare nei sondaggi
|
|