Embed Size (px)
Citation preview
LIGOURAS Panagiote
I.I.S. “Leonardo da Vinci – Galileo Galilei” Noci (BA)
Matematica e Informatica
ESAME DI STATOMatematica Liceo Scientifico
Calcolo Combinator ioI ta l ia , Europa e Amer iche – anni 2011 -2015
Versione 2016.02
Panagiote LIGOURAS 02 / ++ Versione 2016-02
Calcolo Combinatorio
𝐶𝑛,𝑘 =𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1 𝑛 + 1 ! = 𝑛! 𝑛 + 1
𝑃𝑛 = 𝑛!
𝐷𝑛;𝑘 =𝑛!
𝑛 − 𝑘 !𝐷𝑛;𝑘 = 𝑛 𝑛 − 1 𝑛 − 2 … 𝑛 − 𝑘 + 1
𝐷𝑛;𝑘′ = 𝑛𝑘
𝐶𝑛;𝑘′ =
𝑛 + 𝑘 − 1 !
𝑘! 𝑛 − 1 !
𝑥 + 𝑎 𝑛 =
𝑘=0
𝑛𝑛𝑘
𝑥𝑛−𝑘𝑎𝑘
Fattoriale di n
Permutazioni semplici
Disposizioni semplici
Disposizioni con ripetizione
Combinazioni semplici
Combinazioni con ripetizione
Potenza di un binomio
𝑃𝑛𝑘1,𝑘2,…,𝑘𝑛 =
𝑛!
𝑘1! 𝑘2! … 𝑘𝑚!Permutazioni con ripetizioni
𝑛𝑘
=𝑛
𝑛 − 𝑘
𝑛𝑘
=𝑛 − 1𝑘
+𝑛 − 1𝑘 − 1
𝐶𝑛,𝑘′ =
𝑛 + 𝑘 − 1𝑘
Panagiote LIGOURAS 03 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.4 – Italia Comunicazioni – 2011
𝐶𝑛,𝑘 =𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
𝑛
4=
𝑛
3
È sufficiente risolvere l’equazione
con n numero naturale maggiore o uguale a 4.
È sufficiente che sia n – 3 = 4, da cui n = 7
È noto che𝑛
3=
𝑛
𝑛 − 3
𝑛𝑘
=𝑛
𝑛 − 𝑘
Di conseguenza𝑛
4=
𝑛
𝑛 − 3
Panagiote LIGOURAS 04 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.5 – Italia – 2012
I segmenti richiesti sono tanti quante le combinazioni senza ripetizioni di n oggetti a 2 a 2:
Il numero dei triangoli richiesti è pari alle combinazioni senza ripetizioni di n oggetti a 3 a 3:
Il numero dei tetraedri è pari alle combinazioni senza ripetizioni di n oggetti a 4 a 4:
𝐶𝑛,𝑘 =𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
𝑛2
=𝑛!
2! 𝑛 − 2 !=𝑛 ∙ 𝑛 − 1
2!
𝑛3
=𝑛!
3! 𝑛 − 3 !=𝑛 ∙ 𝑛 − 1 ∙ 𝑛 − 2
3!
𝑛4
=𝑛!
4! 𝑛 − 4 !=𝑛 ∙ 𝑛 − 1 ∙ 𝑛 − 2 ∙ 𝑛 − 3
4!
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Panagiote LIGOURAS 05 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.1 – Americhe – 2012
𝐶𝑛,𝑘 =𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
𝐶10,4 =104
=10!
4! 10 − 4 !=
Il numero di scelte è dato dal numero delle combinazioni di 10 oggetti a 4 a 4 che sono tutte le possibili quaterne di studenti fra i 10:
=10!
4! ∙ 6!=
=10 ∙ 9 ∙ 8 ∙ 7
4!=
=10 ∙ 9 ∙ 8 ∙ 7
1 ∙ 2 ∙ 3 ∙ 4=
= 𝟐𝟏𝟎
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Panagiote LIGOURAS 06 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.6 – Americhe – 2012
Essendo consentita la ripetizione, sia la cifra delle decine, sia la cifra delle unità possono essere scelte in 4 modi.
Quindi si hanno 16 possibili numeri.
Infatti, essi sono le disposizioni con ripetizione di 4 oggetti a 2 a 2, date da:
𝐷𝑛;𝑘′ = 𝑛𝑘
𝐷4;2′ = 42 = 𝟏𝟔
Panagiote LIGOURAS 07 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.1 – Europa – 2012
Per definizione, ad ogni elemento di A deve corrispondere uno ed un solo elemento di B ed inoltre ad elementi distinti in A devono corrispondere elementi distinti in B.
Da ciò segue che deve essere 𝑚 ≥ 𝑛 .
Dobbiamo trovare il numero delle coppie ordinate (x, y) con x elemento di A e y elemento di B.
Si può confermare che il numero di tali coppie è uguale al numero delle disposizioni di m oggetti ad n ad n, quindi:
𝐷𝑚;𝑛 =𝑚!
𝑚 − 𝑛 != 𝒎 𝒎− 𝟏 𝒎− 𝟐 … 𝒎− 𝒏 + 𝟏
𝑫𝒏;𝒌 =𝒏!
𝒏 − 𝒌 !
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Panagiote LIGOURAS 08 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.8 – Europa – 2012
Dobbiamo contare i possibili modi con cui possiamo occupare due posti su sei con sette oggetti.
Nel nostro caso gli oggetti sono le cifre 3, 4, 5, 6, 7, 8, 9.
Se le due cifre (oltre a 1 e 2) sono uguali, i possibili numeri, per ognuna delle sette cifre rimanenti, sono uguali alle permutazioni di 6 oggetti di cui 2 uguali fra di loro (1), altri due uguali fra di loro (2) e altri due uguali fra di loro (una delle sette cifre da 3 a 9).
Di conseguenza si ha:𝑃62,2,2 =
6!
2! ∙ 2! ∙ 2!=6 ∙ 5 ∙ 4 ∙ 3 ∙ 2
2 ∙ 2 ∙ 2= 6 ∙ 5 ∙ 3 = 90
𝑃𝑛𝑘1,𝑘2,…,𝑘𝑛 =
𝑛!
𝑘1! 𝑘2! … 𝑘𝑚!
Adesso, considerando le sette cifre a nostra disposizione, avremo 90 x 7 = 630 possibili numeri con due cifre uguali ad 1, due cifre uguali a 2 e due cifre uguali fra di loro (da 3 a 9).
Se le due cifre (oltre a 1 e 2) sono diverse, le coppie possibili con cui possiamo riempire gli altri due posti senza tener conto dell’ordine sono le combinazioni di 7 oggetti a 2 a 2.
Quest’ultimo numero deve essere moltiplicato per le permutazioni di 6 oggetti (le sei cifre), di cui 2 uguali fra di loro (1) e altri 2 uguali fra di loro (2).
Complessivamente avremo:
𝐶𝑛,𝑘 =𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
𝐶7,2 ∙ 𝑃62,2 =
7!
2! 7 − 2 !∙
6!
2! ∙ 2!=
7!
2! ∙ 5!∙
6!
2! ∙ 2!= 21 ∙ 18 = 3780
I numeri che in totale avremo sono:630 + 3780 = 𝟒𝟒𝟏𝟎
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Panagiote LIGOURAS 09 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.6 – Italia – 2013
I 6 numeri più grandi si ottengono da 7654321 permutando le ultime 3 cifre (3!=6).
Al posto n. 5040 abbiamo 7654321
Al posto n. 5039 abbiamo 7654312
Al posto n. 5038 abbiamo 7654231
Al posto n. 5037 abbiamo 7654213
Al posto n. 5036 abbiamo 7654132
Con 1 al primo posto abbiamo 6!=720 numeri,
con 2 al primo posto altri 720;
il numero di posto 1441 è il più piccolo che inizia con 3, cioè 3124567.
𝟕𝟐𝟎 + 𝟕𝟐𝟎 = 𝟏𝟒𝟒𝟎
Panagiote LIGOURAS 10 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.8 – Italia suppletiva – 2013
Nel caso del tetraedro il numero di modi per colorare le 4 facce è dato dalle combinazionisemplici di 10 oggetti a 4 a 4:
Nel caso del cubo il numero di modi per colorare le 6 facce è dato dalle combinazionisemplici di 10 oggetti a 6 a 6:
𝐶𝑛,𝑘 =𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !𝑛𝑘
=𝑛
𝑛 − 𝑘
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Panagiote LIGOURAS 11 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.8 – Italia straordinaria – 2014
Risulta: 𝑛 + 1𝑘 + 1
=𝑛 + 1 !
𝑘 + 1 ! 𝑛 + 1 − 𝑘 + 1 !=
=𝑛 + 1 !
𝑘 + 1 ! 𝑛 − 𝑘 !=
=𝑛! 𝑛 + 1
𝑘! 𝑘 + 1 𝑛 − 𝑘 !=
=𝑛!
𝑘! 𝑛 − 𝑘 !∙𝑛 + 1
𝑘 + 1=
=𝑛𝑘
∙𝑛 + 1
𝑘 + 1
L’uguaglianza risulta verificata solo se
𝐶𝑛,𝑘 =𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Panagiote LIGOURAS 12 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.8 – Americhe – 2014
Il numero 𝑁 dei colori che si possono formare è dato da:
𝐶𝑛,𝑘 =𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
𝐶7,2 =72
=7!
2! 7 − 2 !=
7!
2! 5!=6 ∙ 7
1 ∙ 2= 21
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Panagiote LIGOURAS 13 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.4 – Europa – 2014
Il termine in si ottiene da se
20𝑖
=207
=20!
7! 20 − 7 !=
20!
7! 13!= 77520
𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Panagiote LIGOURAS 14 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.4 – Europa – 2014
𝐶88,3 =883
=88!
3! 88 − 3 !=
88!
3! 85!=
𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
In questo caso basta contare le combinazioni (senza ripetizioni) a 3 a 3 che si possono fare con gli 88 numeri rimanenti:
=88 ∙ 87 ∙ 86
3!=88 ∙ 87 ∙ 86
2 ∙ 3= 𝟏𝟎𝟗𝟕𝟑𝟔
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Panagiote LIGOURAS 15 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.3 – Europa – 2015
5𝑛 + 1
5= 21
𝑛 − 1
4
𝑛𝑘
=𝑛!
𝑘! 𝑛 − 𝑘 !
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 …3 ∙ 2 ∙ 1
Dobbiamo imporre le condizioni: 𝑛 + 1 ≥ 5 → 𝑛 ≥ 4
𝑛 − 1 ≥ 4 → 𝑛 ≥ 5quindi 𝑛 ≥ 5 con n numero naturale
Sviluppando i coefficienti binomiali
5𝑛 + 1 !
5! 𝑛 + 1 − 5 != 21
𝑛 − 1 !
4! 𝑛 − 1 − 4 !𝑛 + 1 ! = 𝑛! 𝑛 + 15
𝑛 + 1 !
5! 𝑛 − 4 != 21
𝑛 − 1 !
4! 𝑛 − 5 !
5𝑛 + 1 !
5! 𝑛 − 5 ! 𝑛 − 4= 21
𝑛 − 1 !
4! 𝑛 − 5 ! 5𝑛 + 1 !
5! 𝑛 − 4= 21
𝑛 − 1 !
4!
5𝑛 + 1 !
4! ∙ 5 ∙ 𝑛 − 4= 21
𝑛 − 1 !
4!𝑛 + 1 !
𝑛 − 4= 21
𝑛 − 1 !
1
𝑛 + 1 ! = 21 𝑛 − 1 ! ∙ 𝑛 − 4
Entrambe le soluzioni sono accettabili perché soddisfano le condizioni su n.
𝑛 − 1 ! ∙ 𝑛 ∙ 𝑛 + 1 = 21 𝑛 − 1 ! ∙ 𝑛 − 4
𝑛 ∙ 𝑛 + 1 = 21 ∙ 𝑛 − 4 𝑛2 − 20𝑛 + 84 = 0 𝒏 = 𝟔 , 𝒏 = 𝟏𝟒
→
→
→
→
→ →
Panagiote LIGOURAS 16 / ++ Versione 2016-02
Calcolo Combinatorio – Quesito n.5 – Italia simulazione – 2015
Per progettare un sito web è necessario generare dei codici unici di accesso. Si vogliono utilizzare, a tale scopo, due lettere maiuscole dell’alfabeto inglese seguite da una serie di numeri compresi tra 0 e 9. Tutti i codici di accesso dovranno avere lo stesso numero di cifre ed è ammessa la ripetizione di lettere e numeri. Qual è il numero minimo di cifre da impostare in modo da riuscire a generare almeno 5 milioni di codici di accesso diversi? Giustificare la risposta.
Quindi n deve essere almeno 4:i codici devono essere formati da almeno 6 caratteri (2 lettere seguite da almeno 4 cifre).
La scelta delle 2 lettere (tra le 26 possibili) è data dalle disposizioni con ripetizioni di 26 oggetti a due a due:
Panagiote LIGOURAS 17 / 17 Versione 2016.02
Grazie!!!
A l b e r o b e l l o
2 0 1 6
Questa presentazione è disponibile anche all’indirizzo:http://www.slideshare.net/panagioteligouras/
Quest’opera è distribuita con licenza Creative Commons Attribuzione - Condividi allo stesso modo 3.0 Italia.
ESAME DI STATO
Matematica
