Economia Domestica

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
EvaristeG
Site Admin
Messaggi: 4771
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Economia Domestica

Messaggio da EvaristeG » 20 lug 2005, 00:14

La mamma di Bobo ha in dispensa n sacchetti di caramelle, ciascuno contenente almeno una caramella.
Per la festa di compleanno dell'adorato figliolo vuole preparare un vassoio con esattamente n caramelle e vorrebbe farlo con il minor spreco possibile, ovvero vuole scegliere k sacchetti tra i suoi n di modo che le caramelle contenute nei k sacchetti siano esattamente n.
Ad occhio, da brava massaia, riesce a dire che il numero totale di caramelle in tutti gli n sacchetti è minore di 2n (strettamente).
E' sempre possibile, in queste condizioni, l'economia domestica sopra spiegata?[/u]

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 20 lug 2005, 07:38

Non sono sicuro di aver capito bene la domanda. Facciamo un esempio.
n=2: in tal caso ci potrebbero essere 2 caramelle in un sacchetto e 1 nell'altro, quindi avrebbe il 50% di possibilità di usare il minor numero di sacchetti possibile (cioè quello in cui ce ne sono direttamente 2) e quindi non è possibile fare "economia domestica"?
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo » 20 lug 2005, 08:50

Direi di sì. Riscrivendo il problema, possiamo dire che in tutti i sacchetti c'è un numero compreso tra 1 e 2 caramelle. Inoltre esiste almeno un sacchetto con una caramella. Dividiamo in due casi:
1)Il numero di sacchetti con due caramelle è minore di [n/2].
Allora basterà semplicemente prendere tutti i sacchetti da 2 e poi tanti sacchetti da 1 quanti ne servono (saranno sufficienti, perchè il numero di caramelle è compreso tra n e 2n)
2)Il numero di sacchetti con 2 caramelle è maggiore di [n/2].
Se n è pari basta prendere n/2 sacchetti. Se n è dispari basta prendere [n/2] sacchetti da 2 e 1 sacchetto da 1. Questo sacchetto da 1 esiste sempre per l'ipotesi.

MindFlyer

Messaggio da MindFlyer » 20 lug 2005, 09:30

Riformulazione:
dati n interi positivi la cui somma è minore di 2n, è sempre possibile sceglierne alcuni in modo che la loro somma sia n?

MindFlyer

Messaggio da MindFlyer » 20 lug 2005, 09:33

@Sisifo: non è vero che in ogni sacchetto ci sono 1 o 2 caramelle, occhio!

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 20 lug 2005, 13:54

Lemma: Essendoe $ n $ un intero positivo, siano $ a_{1, n}, a_{2, n}, \ldots, a_{n, n}\in\mathbb{N}_0 $ ed $ S_n = \sum_{i=1}^n a_{i,n} $. Se $ S_n < 2n $, comunque scelto un $ m = 1, 2, \ldots, n $, esistono $ t \in\mathbb{N}_0 $ e una $ t $-upla $ (i_1, i_2, \ldots, i_t) $ estratta da $ (1, 2, \ldots, n) $ t.c. $ m = \sum_{k=1}^t a_{i_k, n} $.

Dim.: wlog, ammettiamo $ a_{1, n} \leq a_{2, n} \leq \ldots \leq a_{n,n} $ e osserviamo quindi che dev'essere $ a_{n,n} \leq n $, onde procedere di conseguenza per induzione. Se $ n = 1 $, la tesi è banale. Supponendone così la consistenza per un generico $ n\in\mathbb{N}_0 $, distinguiamo fra due possibili alternative: i) $ a_{n+1,n+1} = 1 $, e allora $ \sum_{i=1}^m a_{i,n+1} = m $, per ogni $ m = 1, 2, \ldots, n+1 $, e la tesi è prontamente soddisfatta; ii) $ a_{n+1, n+1} > 1 $, e dunque $ a_{1, n+1}, a_{2, n+1}, \ldots, a_{n, n+1} $ sono $ n $ interi positivi per cui $ \sum_{i=1}^n a_{i, n+1} < 2n $, e come tali (sulla base dell'ipotesi induttiva) si sommano (tutti o in parte) ad ogni intero $ m = 1, 2, \ldots, n $. Se $ a_{n+1, n+1} = n+1 $, null'altro v'è perciò da aggiungere. Se invece $ a_{n+1, n+1} < n+1 $, allora $ 1 \leq n+1 - a_{n+1,n+1} \leq n $, ed esistono $ t \in\mathbb{N}_0 $ e una qualche $ t $-upla $ (i_1, i_2, \ldots, i_t) $ estratta da $ (1, 2, \ldots, n) $ tali che $ \sum_{k=1}^t a_{i_k, n+1} = n+1 - a_{n+1, n+1} $. Di qui l'asserto, q.e.d.
Ultima modifica di HiTLeuLeR il 20 lug 2005, 14:26, modificato 1 volta in totale.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 20 lug 2005, 13:58

MindFlyer ha scritto:Riformulazione: dati n interi positivi la cui somma è minore di 2n, è sempre possibile sceglierne alcuni in modo che la loro somma sia n?
Sì, per conseguenza del simpatico lemmino di cui vi ho fatto omaggio... :mrgreen:

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 20 lug 2005, 14:00

EvaristeG ha scritto:La mamma di Bobo ha in dispensa n sacchetti di caramelle, ciascuno contenente almeno una caramella. Per la festa di compleanno dell'adorato figliolo vuole preparare un vassoio con esattamente n caramelle e vorrebbe farlo con il minor spreco possibile, ovvero vuole scegliere k sacchetti tra i suoi n di modo che le caramelle contenute nei k sacchetti siano esattamente n. Ad occhio, da brava massaia, riesce a dire che il numero totale di caramelle in tutti gli n sacchetti è minore di 2n (strettamente). E' sempre possibile, in queste condizioni, l'economia domestica sopra spiegata?[/u]
Certo che no, povera donna, se il Bobo in questione è sua Aritmeticità in persona... :roll: :lol:

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 20 lug 2005, 14:44

ok, ora che euler ha detto la sua qualcuno trovi la soluzione carina, su :wink:

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 20 lug 2005, 15:36

La mia non ti sembra abbastanza carina, per caso? Ah... Ahah... :twisted:

Avatar utente
NicolasBourbaki
Messaggi: 56
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da NicolasBourbaki » 20 lug 2005, 15:55

Premetto che non ho seguito la storia di Bobo e compagnia bella ...cmq prendo il problema nella sua formulazione meno fantasiosa:
"dato un insieme di n interi aventi somma<2n dire se si può sempre trovare un sottoinsieme avente somma n".

Io direi proprio di sì.

Dim:
-se un termine è multiplo di n (cioè se è uguale ad n,data la condizione sulla somma) abbiamo finito
-else nessuno degli elementi del nostro insieme è multiplo di n.Perciò consideriamo le somme s_1=a_1;s_2=a_1+a_2 (ove a_k per k=1,..,n è il generico termine del nostro insieme ed inoltre a_i<=a_(i+1) per ogni i=1,..,n-1.
Ora si verificherà per tali n somme una delle due seguenti eventualità:
1)almeno una di esse è divisibile per n allora abbiamo finito (dato che,di nuovo questa somma non può che essere proprio n,essendo minore della somma di tutti i termini dell'insieme,che è a sua volta<2n)
2)nessuna somma è divisibile per n,allora per PIGEONHOLE ve ne sono due congrue (mod n),quindi la loro differenza che non può essere nulla dato che stiamo operando con interi positivi dev'essere proprio n,per i motivi già detti.

In ogni caso la tesi è dimostrata.

Saluti BOURBAKI

p.s.
sono di fretta per cui spero di non aver risolto un problema diverso da quello dato!!

EvaristeG
Site Admin
Messaggi: 4771
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 20 lug 2005, 17:52

Uff, Mind mi rovina la storia e Hit la soluzione... bah
Bravo NB, cmq.

MindFlyer

Messaggio da MindFlyer » 20 lug 2005, 20:38

Per me questa è combinatoria...

Rispondi