105.Sempre dalla stessa fonte

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

105.Sempre dalla stessa fonte

Messaggioda Ale99 » 06/01/2016, 16:42

Per ogni intero positivo $n$, determinare il più piccolo intero positivo $k(n)$ con questa proprietà :
perr ogni intero positivo $ d $ e per ogni $d$-upla di numeri reali $ (a_1,...,a_d) ∈ [0,1]^d $ tali $a_1+...+a_d = n $ , è possibile suddividere i $d$ elementi in $k(n)$ gruppi
in maniera tale che la somma dei numeri appartenenti ad ogni gruppo sia sempre minore od uguale ad $1 $
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51

Re: 105.Sempre dalla stessa fonte

Messaggioda lucaboss98 » 06/01/2016, 16:51

Soluzione swag: supponiamo di averli divisi in $m$ gruppi (e che questa sia la cosa migliore) con somme $g_1,\ldots , g_m$. Allora (indici modulo $m$) $$ A = \sum\limits_{i=1}^m (g_i + g_{i+1}) > m $$ infatti ogni gruppo non può essere unito ad un altro per l'ottimalità di $m$.
D'altra parte $$ A= 2 \sum\limits_{i=1}^m g_i = 2n $$
Allora $m<2n \rightarrow m\leq2n-1$ . Dunque si può sempre trovare una divisione in $2n-1$ gruppi.
Dimostriamo ora che c'è un caso in cui si è obbligati a fare $2n-1$ basta prendere $d=2n-1$ e $a_1 = \ldots = a_d = \frac{n}{2n-1} $ infatti la somma di almeno due di loro è $>1$.
lucaboss98
 
Messaggi: 981
Iscritto il: 27/11/2013, 20:03

Re: 105.Sempre dalla stessa fonte

Messaggioda Ale99 » 06/01/2016, 16:58

E io che pensavo durasse almeno 15 minuti ...
Ovviamente puoi andare col prossimo ...
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti