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]
Economia Domestica
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"?
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...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
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.
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
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.
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.
Certo che no, povera donna, se il Bobo in questione è sua Aritmeticità in persona...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]
-
NicolasBourbaki
- Messaggi: 56
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa
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!!
"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!!