Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
Il gioco delle biglie di vetro
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 30 Dic 2009 23:53    Oggetto: Il gioco delle biglie di vetro Rispondi citando

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
Profilo Invia messaggio privato AIM Yahoo MSN
Scrigno
Semidio
Semidio


Registrato: 26/07/09 04:32
Messaggi: 313

MessaggioInviato: 01 Gen 2010 19:15    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 02 Gen 2010 13:59    Oggetto: Rispondi citando

@ Scrigno:

ahinoi, ogni singolo settore (a qualsiasi riga appartenga) deve contenere un numero diverso di biglie
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Scrigno
Semidio
Semidio


Registrato: 26/07/09 04:32
Messaggi: 313

MessaggioInviato: 02 Gen 2010 16:28    Oggetto: Rispondi citando

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 Razz

La 14a riga, dove dice di partire dalla riga con meno biglie (2+2n) Ha bisogno non di una ma di due correzioni Razz

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 Razz 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
Profilo Invia messaggio privato
Jowex
Eroe in grazia degli dei
Eroe in grazia degli dei


Registrato: 15/04/06 14:20
Messaggi: 90

MessaggioInviato: 02 Gen 2010 19:44    Oggetto: Rispondi citando

Secondo me si può fare di meglio, ma ci sto ancora lavorando quindi non mi sbilancio! Very Happy
Top
Profilo Invia messaggio privato
Scrigno
Semidio
Semidio


Registrato: 26/07/09 04:32
Messaggi: 313

MessaggioInviato: 03 Gen 2010 08:40    Oggetto: Rispondi citando

Jowex ha scritto:
Secondo me si può fare di meglio, ma ci sto ancora lavorando quindi non mi sbilancio! Very Happy


In che senso Jowex?
La soluzione non è esatta?
O forse una differente disposizione delle bigle affinchè se ne abbiano di meno?
Top
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 03 Gen 2010 15:34    Oggetto: Rispondi citando

Scrigno ha scritto:
Jowex ha scritto:
Secondo me si può fare di meglio, ma ci sto ancora lavorando quindi non mi sbilancio! Very Happy


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 Wink ) per verificare se è rispettata anche la regola 3) (quella del minimo)
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Jowex
Eroe in grazia degli dei
Eroe in grazia degli dei


Registrato: 15/04/06 14:20
Messaggi: 90

MessaggioInviato: 03 Gen 2010 16:03    Oggetto: Rispondi citando

Sì intendevo proprio ciò che ha scritto Salmastro, la soluzione è giusta ma non è quella che minimizza il numero di biglie usate per ogni riga Wink
Top
Profilo Invia messaggio privato
Jowex
Eroe in grazia degli dei
Eroe in grazia degli dei


Registrato: 15/04/06 14:20
Messaggi: 90

MessaggioInviato: 03 Gen 2010 16:11    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
Jowex
Eroe in grazia degli dei
Eroe in grazia degli dei


Registrato: 15/04/06 14:20
Messaggi: 90

MessaggioInviato: 03 Gen 2010 16:12    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 04 Gen 2010 13:12    Oggetto: Rispondi

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: Applause Applause Applause complimenti
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Pagina 1 di 1

 
Vai a:  
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