Boh mi sono inventato sta cosa, spero sia giusta e non sia un fatto troppo noto (è la generalizzazione di un vecchio esercizio di una gara a squadre):
Sono dati 3 mucchi di sassi contenenti rispettivamente X, Y, Z sassi, e sono permesse le seguenti mosse:
i) Se un gruppo contiene un numero pari di sassi, lo divido in due gruppi contenenti lo stesso numero di sassi ciascuno.
ii) Unisco due gruppi in un gruppo che contiene tutti i sassi dei due gruppi precedenti.
A) Mostrare che è sempre possibile, con una adeguata sequenza di mosse, ottenere $ \frac{X+Y+Z}{MCD(X,Y,Z)} $ gruppi.
B) Mostrare che partendo da $ n>2 $ gruppi ($ a_1, a_2, ..., a_n $) è possibile ottenere $ \displaystyle \frac{\sum_{i=1}^n a_i}{MCD(a_i)} $ gruppi.
Mucchi di sassi
Re: Mucchi di sassi
Problema carino!
Lo faccio prima nel caso $MCD(x,y,z)=1$. Mostro che posso arrivare ad avere $x+y+z$ mucchietti da un sassolino. Mostro per induzione che dati $n$ mucchietti c'è sempre una sequenza di mosse che me ne fa fare $n+1$.
Con 3 mucchietti faccio il caso base. Se ce n'è uno pari lo divido in due e ottengo 4 mucchietti e fine. Se sono tutti dispari faccio questo giochetto: ne unisco due e poi divido il mucchio totale in altri due mucchi. In poche parole $(x,y,z) \Rightarrow (\dfrac{x+y}{2},\dfrac{x+y}{2},z)$ [Edit: Attenzione! Qui bisogna controllare delle ipotesi che non sempre sono verificate e che rendono sbagliato questo procedimento. Vedi i messaggi più in basso]. Se ora ce n'è uno pari lo divido in due e ottengo 4 mucchietti e fine. Altrimenti rifaccio il giochetto di prima. Continuando a fare il giochetto, vorrei che ad un certo punto, quando divido in due, un mucchietto ottenuto fosse pari. Suppongo per assurdo che non sia così e che possa fare il gioco all'infinito ottenendo sempre interi dispari. In realtà così non è perché col crescere di $n$ quei termini "si avvicinano sempre di più" sfiorandolo $\dfrac{x+y+z}{3}$, facendo sì che sia impossibile che quei termini rimangano sempre interi (posso scrivere più formalmente questa parte, ma l'idea è che scegliendo $n$ opportunamente grande quei numeri vengono schiacciati su $\dfrac{x+y+z}{3}$ e quindi non possono essere interi). Dunque dopo un certo numero di volte che è stato fatto questo gioco, si otterranno due mucchietti pari e quindi dividendo in due si ottengono 4 mucchietti e fine.
Per il passo induttivo se fra gli $n$ ce n'è uno pari splitto e ce ne ho $n+1$. Altrimenti se sono tutti dispari ne prendo $3$ e faccio il gioco di prima.
In questa maniera riesco a fare sempre più mucchietti, fino al massimo possibile che è x+y+z. La somma, infatti, è invariante facendo le mosse e quindi rimane costante. Inoltre non può esistere un mucchietto che ha 0 sassi dunque il massimo è x+y+z che si riesce a raggiungere, finendo con x+y+z mucchietti di 1.
Nel caso $MCD(x,y,z) = d \neq 1$, col procedimento di prima riesco a finire con $\dfrac{x+y+z}{d}$ mucchietti da $d$ ciascuno.
Per il caso generale (con $(a_1,...,a_n)=1$) basta ordinare $a_1\leqa_2\leq...\leqa_n$. Poi si prendono gli ultimi 3 e si riducono a $a_{n-2}+a_{n-1}+a_{n}$ uni. Alcuni di questi si possono aggiungere a $a_{n-3}$ per raggiungere la potenza di due più vicina e poi quella potenza di due si può smembrare facendola diventare tutti 1...e così via si riesce ad avvere tutti 1.
Questo è possibile perché $a_{n-3}=2^k+s$ con $0\leq s\leq2^k-1$ e voglio mostrare che $a_{n-2}+a_{n-1}+a_n \geq 2^k-s$. Questo è vero perché $a_{n-2}+a_{n-1}+a_n > a_{n-2} \geq a_{n-3} =2^k+s \geq 2^k-s$. Nel caso $(a_1,...,a_n)\neq 1$ è identico.
Spero sia chiaro e giusto
Lo faccio prima nel caso $MCD(x,y,z)=1$. Mostro che posso arrivare ad avere $x+y+z$ mucchietti da un sassolino. Mostro per induzione che dati $n$ mucchietti c'è sempre una sequenza di mosse che me ne fa fare $n+1$.
Con 3 mucchietti faccio il caso base. Se ce n'è uno pari lo divido in due e ottengo 4 mucchietti e fine. Se sono tutti dispari faccio questo giochetto: ne unisco due e poi divido il mucchio totale in altri due mucchi. In poche parole $(x,y,z) \Rightarrow (\dfrac{x+y}{2},\dfrac{x+y}{2},z)$ [Edit: Attenzione! Qui bisogna controllare delle ipotesi che non sempre sono verificate e che rendono sbagliato questo procedimento. Vedi i messaggi più in basso]. Se ora ce n'è uno pari lo divido in due e ottengo 4 mucchietti e fine. Altrimenti rifaccio il giochetto di prima. Continuando a fare il giochetto, vorrei che ad un certo punto, quando divido in due, un mucchietto ottenuto fosse pari. Suppongo per assurdo che non sia così e che possa fare il gioco all'infinito ottenendo sempre interi dispari. In realtà così non è perché col crescere di $n$ quei termini "si avvicinano sempre di più" sfiorandolo $\dfrac{x+y+z}{3}$, facendo sì che sia impossibile che quei termini rimangano sempre interi (posso scrivere più formalmente questa parte, ma l'idea è che scegliendo $n$ opportunamente grande quei numeri vengono schiacciati su $\dfrac{x+y+z}{3}$ e quindi non possono essere interi). Dunque dopo un certo numero di volte che è stato fatto questo gioco, si otterranno due mucchietti pari e quindi dividendo in due si ottengono 4 mucchietti e fine.
Per il passo induttivo se fra gli $n$ ce n'è uno pari splitto e ce ne ho $n+1$. Altrimenti se sono tutti dispari ne prendo $3$ e faccio il gioco di prima.
In questa maniera riesco a fare sempre più mucchietti, fino al massimo possibile che è x+y+z. La somma, infatti, è invariante facendo le mosse e quindi rimane costante. Inoltre non può esistere un mucchietto che ha 0 sassi dunque il massimo è x+y+z che si riesce a raggiungere, finendo con x+y+z mucchietti di 1.
Nel caso $MCD(x,y,z) = d \neq 1$, col procedimento di prima riesco a finire con $\dfrac{x+y+z}{d}$ mucchietti da $d$ ciascuno.
Per il caso generale (con $(a_1,...,a_n)=1$) basta ordinare $a_1\leqa_2\leq...\leqa_n$. Poi si prendono gli ultimi 3 e si riducono a $a_{n-2}+a_{n-1}+a_{n}$ uni. Alcuni di questi si possono aggiungere a $a_{n-3}$ per raggiungere la potenza di due più vicina e poi quella potenza di due si può smembrare facendola diventare tutti 1...e così via si riesce ad avvere tutti 1.
Questo è possibile perché $a_{n-3}=2^k+s$ con $0\leq s\leq2^k-1$ e voglio mostrare che $a_{n-2}+a_{n-1}+a_n \geq 2^k-s$. Questo è vero perché $a_{n-2}+a_{n-1}+a_n > a_{n-2} \geq a_{n-3} =2^k+s \geq 2^k-s$. Nel caso $(a_1,...,a_n)\neq 1$ è identico.
Spero sia chiaro e giusto
Ultima modifica di bĕlcōlŏn il 14 giu 2011, 10:57, modificato 2 volte in totale.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: Mucchi di sassi
Bravo, lo ho fatto preticamente come te! 
Solo che mi è venuto in mente ieri sera che bisognerebbe mostrare che quando fai la mossa $ (x,y,z) \rightarrow (\frac{x+y}{2}, \frac{x+y}{2}, z) $ queste 3 quantità che ottieni non siano uguali (e questo si mostra facilmente) ma anche che non abbiano un $ MCD > 1 $ altrimenti chiaramente non ci va più bene.
Faccio un esempio per spiegarmi meglio: partendo da 3, 5, 7 posso sommare 3 e 5 e vinco ma se parto invece sommando 3 e 7 poi divido il 10 ottengo 5, 5, 5 da cui non esco più.
Cioè quello che servirebbe è mostrare che dati 3 numeri $ x,y,z $ coprimi tra loro almeno una delle coppie $ (x+y, z) $, $ (x+z, y) $ e $ (y+z, x) $ abbia $ MCD =1 $
Solo che mi è venuto in mente ieri sera che bisognerebbe mostrare che quando fai la mossa $ (x,y,z) \rightarrow (\frac{x+y}{2}, \frac{x+y}{2}, z) $ queste 3 quantità che ottieni non siano uguali (e questo si mostra facilmente) ma anche che non abbiano un $ MCD > 1 $ altrimenti chiaramente non ci va più bene.
Faccio un esempio per spiegarmi meglio: partendo da 3, 5, 7 posso sommare 3 e 5 e vinco ma se parto invece sommando 3 e 7 poi divido il 10 ottengo 5, 5, 5 da cui non esco più.
Cioè quello che servirebbe è mostrare che dati 3 numeri $ x,y,z $ coprimi tra loro almeno una delle coppie $ (x+y, z) $, $ (x+z, y) $ e $ (y+z, x) $ abbia $ MCD =1 $
Re: Mucchi di sassi
Hai ragione, avevo fatto tutto molto a cuor leggero, senza controllare Il problema è che la tua ultima congettura è falsa, prendi (155,69,91). Il loro MCD è 1, ma (224,91)=7, (246,69)=3 e (160,155)=5...
Il problema iniziale fra l'altro diventa falso...
Con (155,69,91) non riuscirai mai a raggiungere 315 gruppi, perché dopo il primo passo hai già il fattore in più che rompe e che ti porti dietro fino alla fine. Al più ne fai 105.
Non penso si possa riformulare in maniera sensata, comunque, i mucchietti finali fanno un po' come vogliono
Il problema è che la tua ultima congettura è falsa, prendi (155,69,91). Il loro MCD è 1, ma (224,91)=7, (246,69)=3 e (160,155)=5...Il problema iniziale fra l'altro diventa falso...
Con (155,69,91) non riuscirai mai a raggiungere 315 gruppi, perché dopo il primo passo hai già il fattore in più che rompe e che ti porti dietro fino alla fine. Al più ne fai 105.
Non penso si possa riformulare in maniera sensata, comunque, i mucchietti finali fanno un po' come vogliono
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: Mucchi di sassi
Eh già! Cavolo mi spiace averti fatto lavorare su un problema sbagliato, come detto mi son accorto solo ieri sul tardi dell'errore.. 