[L03] I turchi mettono a soqquadro i numeri

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

[L03] I turchi mettono a soqquadro i numeri

Messaggioda Gerald Lambeau » 28/04/2016, 20:10

Trovare il numero di $(a_1, a_2, \dots, a_{2016})$ permutazioni di $(1, 2, \dots, 2016)$ tali che, per tutti gli $1 \le i<j \le 2016$, $i+a_i \le j+a_j$.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 848
Iscritto il: 07/01/2015, 18:18

Re: [L03] I turchi mettono a soqquadro i numeri

Messaggioda Ale99 » 05/03/2017, 11:55

Sinceramente non so come io sia finito qua però già che ci siamo mettiamo un'idea a questo problema innocente e che mi sembra strano venga da una gara turca ...

Errata
Ultima modifica di Ale99 il 05/03/2017, 19:20, modificato 1 volta in totale.
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: [L03] I turchi mettono a soqquadro i numeri

Messaggioda Gerald Lambeau » 05/03/2017, 18:46

Il risultato è sbagliato.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 848
Iscritto il: 07/01/2015, 18:18

Re: [L03] I turchi mettono a soqquadro i numeri

Messaggioda Ale99 » 05/03/2017, 19:07

Ok meglio se lo riguardo con calma ... :oops:
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: [L03] I turchi mettono a soqquadro i numeri

Messaggioda Roob » 06/03/2017, 20:06

Sperando che sia giusto...
Chiamiamo [tex]P_n[/tex] il numero di suddette permutazioni per [tex]n[/tex] qualsiasi.
Osserviamo che per soddisfare la richiesta una qualsiasi permutazione deve avere che
[tex]a_i\leq a_{i+1} +1[/tex] (1)
che segue dalla richiesta sostituendo [tex]j=i+1[/tex]. Questa condizione è necessaria ma anche sufficiente, poiché fa sì che la [tex]n[/tex]-upla degli [tex]i+a_i[/tex] sia debolmente crescente, come richiesto.
Prendendo una qualunque permutazione adatta lunga [tex]n-1[/tex], possiamo ottenerne una lunga [tex]n[/tex] aggiungendo [tex]n[/tex] o alla fine o prima di [tex]n-1[/tex], altrimenti non soddisferemmo (1). Poiché con questo metodo otteniamo tutte le permutazioni lunghe [tex]n[/tex] senza prenderne nessuna 2 volte, e ad ognuna lunga [tex]n-1[/tex] ne abbiamo associate 2, si ha che
[tex]P_n=2P_{n-1}[/tex]
E poiché [tex]P_1=1[/tex], [tex]P_n=2^{n-1}[/tex]
E in particolare [tex]P_{2016}=2^{2015}[/tex]
Ultima modifica di Roob il 06/03/2017, 20:59, modificato 1 volta in totale.
Roob
 
Messaggi: 25
Iscritto il: 23/11/2016, 16:52

Re: [L03] I turchi mettono a soqquadro i numeri

Messaggioda Gerald Lambeau » 06/03/2017, 20:58

Giusta!
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 848
Iscritto il: 07/01/2015, 18:18


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite