ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ PDF

ΒΑΓΓΕΛΗΣ ΨΥΧΑΣ ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 1 Β Α Σ Ι Κ ΕΣ Α Ρ Χ Ε Σ Α Π Α Ρ Ι Θ Μ Η Σ Η Σ Συνδυαστική είναι ο κλάδος των μαθηματικών που ασχολείται με την καταμέτρηση (απαρίθμηση) των στοιχείων διαφόρων συνόλων. Τα τελευταία χρόνια η συνδυαστική αποτελεί τμήμα ενός ευρύτερου κλάδου των μαθηματικών...

ΒΑΓΓΕΛΗΣ ΨΥΧΑΣ ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 1 Β Α Σ Ι Κ ΕΣ Α Ρ Χ Ε Σ Α Π Α Ρ Ι Θ Μ Η Σ Η Σ Συνδυαστική είναι ο κλάδος των μαθηματικών που ασχολείται με την καταμέτρηση (απαρίθμηση) των στοιχείων διαφόρων συνόλων. Τα τελευταία χρόνια η συνδυαστική αποτελεί τμήμα ενός ευρύτερου κλάδου των μαθηματικών που ονομάζονται “Διακριτά μαθηματικά”. 1. 1 Α Ρ Χ Η Τ Ο Υ Α Θ Ρ Ο Ι Σ Μ Α ΤΟ Σ Ø Αν ένα αντικείμενο α i μπορεί να εκλεγεί με κ i τρόπους, i = 1,2 ,3 ,… ,ν και η εκλογή του α i αποκλείει τη ταυτόχρονη εκλογή του α j i , j = 1 ,2 ,3 ,… ,ν i ≠ j τότε οποιοδήποτε από τα α 1 ή α 2 ή α 3 ή......, ή αν μπορεί να επιλεγεί με κ 1 + κ 2 + + κ ν τρόπους. 1. 2 Π Ρ Ο Β Λ Η ΜΑ ( Α ΡΧ Η Τ Ο Υ ΑΘ ΡΟ Ι Σ ΜΑ ΤΟ Σ ) Ø Διαθέτουμε 4 διαφορετικά τετράδια και 5 διαφορετικά στυλό. Με πόσους τρόπους κάποιος μαθητής μπορεί να διαλέξει ένα τετράδιο ή ένα στυλό; Απάντηση Το τετράδιο (αντικείμενο α 1 ), ο μαθητής μπορεί να το επιλέξει με κ 1 = 4 τρόπους και η εκλογή του αποκλείει την εκλογή στυλό (αντικείμενο α 2 ). Το στυλό (αντικείμενο α 2 ), ο μαθητής μπορεί να το επιλέξει με κ 2 = 5 τρόπους και η εκλογή του αποκλείει την εκλογή τετραδίου (αντικείμενο α 1 ). Άρα οποιοδήποτε από τα α 1 ή α 2 μπορεί να το επιλέξει με κ 1 + κ 2 = 4 + 5 = 9 τρόπους. 1. 3 Π Ρ Ο Β Λ Η ΜΑ ( Α ΡΧ Η Τ Ο Υ ΑΘ ΡΟ Ι Σ ΜΑ ΤΟ Σ ) Ø Τετράγωνο πλευράς μήκους 6 , το χωρίζουμε με παράλληλες ευθείες σε 36 τετράγωνα πλευράς μήκους 1 (όπως φαίνεται στο διπλανό σχήμα). Πόσα συνολικά τετράγωνα (που οι πλευρές τους είναι παράλληλες με τις πλευρές του αρχικού τετραγώνου), ορίζονται (δημιουργούνται) μετά από αυτό το χωρισμό; Λύση Σε κάθε πλευρά του τετραγώνου θεωρούμε 5 σημεία που (μαζί με τις κορυφές του), τις χωρίζουν σε έξι ίσα ευθύγραμμα τμήματα. Τα παράλληλα προς τις πλευρές ευθύγραμμα τμήματα τέμνονται σε 25 σημεία. Έτσι στο δημιουργούμενο σχηματισμό (που ονομάζεται και “τετραγωνικό πλέγμα”) έχουμε 49 σημεία, που θα αποτελέσουν τις κορυφές των τετραγώνων. Το τετράγωνο χωρίζεται αρχικά σε τετράγωνα τύπου T1 (που η πλευρά τους έχει μήκος 1). Με κορυφές τα σημεία του “πλέγματος” παρατηρούμε ότι δημιουργούνται τετράγωνα τύπου T2 (που η πλευρά τους έχει μήκος 2), τετράγωνα τύπου T3 (που η πλευρά τους έχει μήκος 3), τετράγωνα τύπου T4 (που η πλευρά τους έχει μήκος 4 ), τετράγωνα τύπου T5 (που η πλευρά τους έχει μήκος 5 ) και τέλος δημιουργείται το αρχικό τετράγωνο που μπορεί να χαρακτηριστεί ως τετράγωνο τύπου T6 (δηλαδή η πλευρά του έχει μήκος 6 ). -2 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Το πλήθος των τετραγώνων τύπου T1 είναι προφανώς 6 2 = 36. Το πλήθος των τετραγώνων τύπου T2 είναι ( 6 − 1 )2 = 5 2 = 25. (Βρείτε όλους τους δυνατούς τρόπους που μπορούμε να τοποθετήσουμε το τετράγωνο τύπου T2 , μέσα στο μεγάλο τετράγωνο ή μετρήστε τα σημεία που μπορεί να είναι κέντρα των τετραγώνων τύπου T2 ). Το πλήθος των τετραγώνων τύπου T3 είναι ( 6 − 2 )2 = 4 2 = 16. (Βρείτε όλους τους δυνατούς τρόπους που μπορούμε να τοποθετήσουμε το τετράγωνο τύπου T3 , μέσα στο μεγάλο τετράγωνο ή μετρήστε τα σημεία που μπορεί να είναι κέντρα των τετραγώνων τύπου T3 ). Το πλήθος των τετραγώνων τύπου T4 είναι ( 6 − 3 )2 = 32 = 9. (Βρείτε όλους τους δυνατούς τρόπους που μπορούμε να τοποθετήσουμε το τετράγωνο τύπου T4 , μέσα στο μεγάλο τετράγωνο ή μετρήστε τα σημεία που μπορεί να είναι κέντρα των τετραγώνων τύπου T4 ). -3 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Το πλήθος των τετραγώνων τύπου T5 είναι ( 6 − 4 )2 = 2 2 = 4. (Βρείτε όλους τους δυνατούς τρόπους που μπορούμε να τοποθετήσουμε το τετράγωνο τύπου T5 , μέσα στο μεγάλο τετράγωνο ή μετρήστε τα σημεία που μπορεί να είναι κέντρα των τετραγώνων τύπου T5 ). Τέλος δημιουργείται ένα μόνο τετράπλευρο τύπου T6 (το αρχικό τετράγωνο). 6( 6 + 1 )( 2 ⋅ 6 + 1 ) Άρα δημιουργούνται συνολικά 12 + 2 2 + 3 2 + 4 2 + 5 2 + 6 2 = = 91 το πλήθος 6 τετράγωνα. 1. 4 Π Ρ Ο Β Λ Η ΜΑ ( Α ΡΧ Η Τ Ο Υ ΑΘ ΡΟ Ι Σ ΜΑ ΤΟ Σ ) Ø Τετράγωνο πλευράς ν , το χωρίζουμε με παράλληλες ευθείες σε ν 2 τετράγωνα πλευράς 1. Πόσα συνολικά τετράγωνα ορίζονται (που οι πλευρές τους είναι παράλληλες με τις πλευρές του αρχικού τετραγώνου) μετά από αυτό το χωρισμό; Απάντηση Το τετράγωνο χωρίζεται σε τετράγωνα τύπου T1 (που η πλευρά τους έχει μήκος 1 ), σε τετράγωνα τύπου T2 (που η πλευρά τους έχει μήκος 2 ), σε τετράγωνα τύπου T3 (που η πλευρά τους έχει μήκος 3 ) και …σε τετράγωνα τύπου Tν (που η πλευρά τους έχει μήκος ν ). Το πλήθος των τετραγώνων τύπου T1 είναι ν 2. Το πλήθος των τετραγώνων τύπου T2 είναι (ν − 1 )2. (Βρείτε όλους τους δυνατούς τρόπους που μπορούμε να τοποθετήσουμε το τετράγωνο τύπου T2 , μέσα στο μεγάλο τετράγωνο). Το πλήθος των τετραγώνων τύπου T3 είναι (ν − 2 ) 2. (Βρείτε όλους τους δυνατούς τρόπους που μπορούμε να τοποθετήσουμε το τετράγωνο τύπου T3 , μέσα στο μεγάλο τετράγωνο). Τέλος δημιουργείται ένα μόνο τετράγωνο τύπου Tν. ν (ν + 1 )( 2ν + 1 ) Άρα δημιουργούνται συνολικά 12 + 2 2 + + ν 2 = το πλήθος τετράγωνα. 6 1. 5 Π Ο Λ ΛΑ ΠΛ Α Σ Ι ΑΣ Τ Ι Κ Η ΑΡΧ Η Ø Αν ένα αντικείμενο α 1 μπορεί να εκλεγεί με κ 1 τρόπους και για κάθε ένα από αυτούς τους τρόπους ένα αντικείμενο α 2 μπορεί να εκλεγεί με κ 2 τρόπους …..και για κάθε ένα από αυτούς τους τρόπους ένα αντικείμενο α ν μπορεί να εκλεγεί με κ ν τρόπους, τότε όλα τα -4 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ αντικείμενα α 1 και α 2 και α 3 και......, και αν μπορούν να επιλεγούν με κ 1 ⋅ κ 2 ⋅ ⋅ κν τρόπους. 1. 6 Π Α Ρ Α Δ Ε Ι Γ ΜΑ (Π Ο Λ ΛΑ ΠΛ Α Σ Ι ΑΣ Τ Ι Κ Η ΑΡΧ Η ) Ø Διαθέτουμε ένα καλάθι που περιέχει ένα πορτοκάλι, ένα μήλο και ένα αχλάδι. Με πόσους τρόπους μπορούμε να διαλέξουμε δύο φρούτα και να τα δώσουμε σε δύο παιδιά; Απάντηση Το πρώτο φρούτο (αντικείμενο α 1 ), μπορούμε να το διαλέξουμε με κ 1 = 3 διαφορετικούς τρόπους (διότι υπάρχουν 3 διαφορετικά φρούτα στο καλάθι) και για κάθε ένα από αυτούς τους τρόπους μπορούμε να διαλέξουμε το δεύτερο φρούτο (αντικείμενο α 2 ), με κ 2 = 2 τρόπους (διότι υπάρχουν 2 διαφορετικά φρούτα στο καλάθι μετά την εκλογή του πρώτου φρούτου). Άρα και τα δύο αντικείμενα (φρούτα) α 1 και α 2 μπορούμε να τα επιλέξουμε με κ 1κ 2 = 3 ⋅ 2 τρόπους. Παρατήρηση Για να γίνει περισότερο κατανοητή η πολλαπλασιαστική αρχή, θα βρούμε με τη βοήθεια των δενδροδιαγραμμάτων όλους τους δυνατούς τρόπους επιλογής των φρούτων. Συντομογραφικά, όλοι οι δυνατοί τρόποι επιλογής των φρούτων είναι: ΑΜ,ΑΠ,ΜΑ,ΜΠ,ΠΑ,ΠΜ. 1. 7 Π Α Ρ Α Δ Ε Ι Γ ΜΑ ( Π Ο ΛΛ ΑΠ Λ ΑΣ Ι ΑΣ ΤΙ Κ Η Α Ρ Χ Η ) Ø Πόσους περιττούς τριψήφιους αριθμούς (με μη επαναλαμβανόμενα ψηφ ία) μπορούμε να δημιουργήσουμε, χρησιμοποιώντας τους αριθμούς 1,2 ,5 ,6 ,8 ,9 ; Απάντηση Όλοι οι αριθμοί που διαθέτουμε είναι έξι και τρείς από αυτούς είναι περιττοί. Το τελευταίο ψηφίο του αριθμού που θα δημιουργήσουμε μπορούμε να το επιλέξουμε με τρείς διαφορετικούς τρόπους από τους 1,5,9 (εφόσον θέλουμε ο αριθμός να είναι περιττός). Το δεύτερο ψηφίο του αριθμού μπορούμε να το διαλέξουμε με πέντε διαφορετικούς τρόπους (διότι θα απομείνουν πέντε αριθμοί προς επιλογή μετά την εκλογή του τελευταίου ψηφίου). Το πρώτο ψηφίο του αριθμού μπορούμε να το επιλέξουμε με τέσσερεις διαφορετικούς τρόπους. Άρα μπορούμε να δημιουργήσουμε 3 ⋅ 4 ⋅ 5 = 60 τριψήφιους περιττούς αριθμούς. -5 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 1. 8 Δ Ι Α ΤΑ Ξ Ε Ι Σ Ø Διατάξεις των ν αντικειμένων ανά κ είναι οι τρόποι με τους οποίους μπορούμε να επιλέξουμε κ το πλήθος αντικείμενα από ένα σύνολο ν αντικειμένων και να τα τοποθετήσουμε στη σειρά. Το πλήθος των διατάξεων των ν αντικειμένων ανά κ είναι: ν ⋅ (ν − 1 ) ⋅ (ν − 2 ) (ν − κ + 1 ) και το συμβολίζουμε με P (ν ,κ ) ή ( ν )κ. Χρησιμοποιώντας το συμβολισμό 1 ⋅ 2 ⋅ 3 ν = ν ! έχουμε: ν! P (ν , κ ) =. (ν − κ )! 1. 9 Π Α Ρ Α Δ Ε Ι Γ Μ Α ( Δ Ι Α ΤΑ Ξ Ε ΙΣ ) Ø Πόσους τριψήφιους αριθμούς (με μη επαναλαμβανόμενα ψηφία) μπορούμε να δημιουργήσουμε, χρησιμοποιώντας τους αριθμούς 1,2 ,3 ,4 ,5 ,6 ; Απάντηση Το πλήθος των τριψηφίων αριθμών που μπορούμε να δημιουργήσουμε, ισούται με τις διατάξεις των 6 αριθμών (που μας δίνονται) ανά 3. 6! 6! 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 Δηλαδή: P( 6 ,3 ) = = = = 4 ⋅ 5 ⋅ 6 = 120. ( 6 − 3 )! 3! 1⋅ 2 ⋅3 Παρατήρηση Το πρόβλημα μπορεί να αντιμετωπιστεί και με τη βοήθεια της πολλαπλασιαστικής αρχής. Το πρώτο ψηφίο μπορεί να επιλεγεί με 6 τρόπους. Το δεύτερο ψηφίο μπορεί να επιλεγεί με 5 τρόπους. Το τρίτο ψηφίο μπορεί να επιλεγεί με 4 τρόπους. Άρα ο τριψήφιος αριθμός μπορεί να επιλεγεί με 6 ⋅ 5 ⋅ 4 = 120 τρόπους. 1.10 Ε Π Α Ν Α Λ Η Π Τ ΙΚ Ε Σ Δ Ι Α Τ Α Ξ Ε Ι Σ Ø Το πλήθος των διατάξεων ν αντικειμένων ανά κ με επανάληψη (χωρίς περιορισμό) το συμβολίζουμε με Ε (ν ,κ ) και δίνεται από τη σχέση: Ε (ν , κ ) = ν κ. 1. 1 1 Π Α Ρ Α Δ Ε Ι Γ Μ Α ( Ε Π Α Ν Α Λ Η Π Τ ΙΚ Ε Σ Δ Ι Α Τ Α Ξ Ε Ι Σ ) Ø Πόσους τριψήφιους αριθμούς μπορούμε να δημιουργήσουμε, χρησιμοποιώντας τους αριθμούς 1,2 ,3 ,4 ,5 ,6 ; Απάντηση Το πλήθος των τριψηφίων αριθμών που μπορούμε να δημιουργήσουμε, ισούται με τις επαναληπτικές διατάξεις των 6 αριθμών (που μας δίνονται) ανά 3. Δηλαδή: Ε ( 6 ,3 ) = 6 3 = 216. Παρατήρηση Το πρόβλημα μπορεί να αντιμετωπιστεί και με τη βοήθεια της πολλαπλασιαστικής αρχής. Το πρώτο ψηφίο μπορεί να επιλεγεί με 6 τρόπους. Το δεύτερο ψηφίο μπορεί να επιλεγεί με 6 τρόπους. Το τρίτο ψηφίο μπορεί να επιλεγεί με 6 τρόπους. -6 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Άρα ο τριψήφιος αριθμός μπορεί να επιλεγεί με 6 ⋅ 6 ⋅ 6 = 216 τρόπους. (Το δεύτερο και το τρίτο ψηφίο μπορούν να επιλεγούν με 6 τρόπους διότι δεν υπάρχει κανένας περιορισμός για τη δημιουργία του τριψήφιου αριθμού) 1. 1 2 Π Α Ρ Α Δ Ε Ι Γ Μ Α ( Ε Π Α Ν Α Λ Η Π Τ ΙΚ Ε Σ Δ Ι Α Τ Α Ξ Ε Ι Σ ) Ø Δέκα άτομα βρίσκονται στον ανελκυστήρα (ασανσέρ) ενός επταόροφου κτιρίου. Ο ανελυστήρας ξεκινά από το ισόγειο και όλοι οι επιβάτες κατεβαίνουν σε κάποιο όροφο. Με πόσους τρόπους μπορούν να κατεβούν οι επιβάτες στους επτά ορόφους; Απάντηση Το πλήθος των τρόπων ισούται με τις επαναληπτικές διατάξεις των 7 ορόφων ανά 10. Δηλαδή: Ε ( 7 ,10 ) = 7 10. Παρατήρηση Το πρόβλημα μπορεί να αντιμετωπιστεί και με τη βοήθεια της πολλαπλασιαστικής αρχής. Το πρώτο άτομο μπορεί να κατεβεί με 7 διαφορετικούς τρόπους. Το δεύτερο άτομο μπορεί να κατεβεί με 7 διαφορετικούς τρόπους. ………. Το δέκατο άτομο μπορεί να κατεβεί με 7 διαφορετικούς τρόπους. Άρα οι επιβάτες μπορούν να κατεβούν 7 ⋅ 7 ⋅ 7 ⋅ ⋅ 7 = 7 10 τρόπους. 1. 1 3 Π Ρ Ο Β Λ Η Μ Α ( Ε Π Α Ν Α Λ Η Π Τ ΙΚ Ε Σ Δ Ι Α Τ Α Ξ Ε ΙΣ ) Ø Με πόσους τρόπους μπορούν να καταλύσουν δέκα τουρίστες, στα επτά ξενοδοχεία μιάς πόλης ; Απάντηση Η ίδια ακριβώς λύση με το προηγούμενο πρόβλημα. 1. 1 4 Μ Ε Τ ΑΘ Ε Σ Ε Ι Σ Ø Μεταθέσεις των ν αντικειμένων είναι οι διατάξεις των ν αντικειμένων ανά ν. Δηλαδή είναι οι τρόποι με τους οποίους μπορούμε να διατάξουμε ν διαφορετικά μεταξύ τους αντικείμενα. Το πλήθος των μεταθέσεων ν αντικειμένων συμβολίζεται με Ρ (ν ) και δίνεται από τη σχέση Ρ (ν ) = ν !. 1. 1 5 Ε Π ΑΝ Α ΛΗ Π ΤΙ Κ Ε Σ Μ Ε ΤΑ Θ Ε Σ Ε Ι Σ Ø Το πλήθος των μεταθέσεων ν ειδών αντικειμένων με κ 1 ,κ 2 , ,κ ν στοιχεία αντίστοιχα το συμβολίζουμε με Μ ( κ 1 , κ 2 , ,κ ν ) και δίνεται από τη σχέση: (κ1 + κ2 + + κ ν )! Μ ( κ 1 ,κ 2 , ,κν ) =. κ 1 !κ 2 ! κν ! 1. 1 6 ΣΥ Ν Δ Υ Α Σ ΜΟ Ι Ø Συνδυασμοί των ν αντικειμένων ανά κ είναι οι τρόποι με τους οποίους μπορούμε να επιλέξουμε κ το πλήθος αντικείμενα από ένα σύνολο ν αντικειμένων. (Στη περίπτωση των συνδυασμών δεν μας ενδιαφέρει η διάταξη επιλογής ή τοποθέτησης των κ επιλεγόμενων αντικειμένων). -7 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ ⎛ν ⎞ Τους συνδυασμούς των ν αντικειμένων ανά κ , τους συμβολίζουμε με C (ν , κ ) ή ⎜⎜ ⎟⎟ και ⎝κ ⎠ ⎛ν ⎞ ν! δίνεται από τη σχέση: C (ν , κ ) = ⎜⎜ ⎟⎟ =. ⎝ κ ⎠ (ν − κ )! κ ! 1.17 Π Α ΡΑ Δ Ε Ι ΓΜ Α ( ΣΥ Ν Δ Υ ΑΣ Μ Ο Ι ) Ø Με πόσους τρόπους ένας προπονητής μίας ομάδας μπάσκετ μπορεί να επιλέξει την αρχική πεντάδα, από τους δώδεκα παίχτες που έχει στη διάθεσή του; Απάντηση Οι τρόποι με τους οποίους ο προπονητής μπορεί να επιλέξει την αρχική πεντάδα (επειδή δεν μας ενδιαφέρει η σειρά με την οποία θα επιλεγούν οι παίχτες) είναι όσοι οι συνδυασμοί των 12 αντικειμένων (παίχτες) ανά 5. Δηλαδή υπάρχουν: ⎛ 12 ⎞ 12! 12! 8 ⋅ 9 ⋅ 10 ⋅ 11 ⋅ 12 C( 12 ,5 ) = ⎜⎜ ⎟⎟ = = = = 5 ⎝ ⎠ ( 12 − 5 )! 5! 7 !5! 1⋅ 2 ⋅ 3 ⋅4 ⋅ 5 9 ⋅ 10 ⋅ 11 ⋅ 12 3 ⋅ 10 ⋅ 11 ⋅ 12 = = = 3 ⋅ 2 ⋅ 11.12 = 72 ⋅ 11 = 792 3⋅5 5 τρόποι επιλογής της αρχικής πεντάδας. 1. 1 8 Ε Π ΑΝ Α ΛΗ Π ΤΙ Κ Ο Ι ΣΥ Ν Δ Υ ΑΣ ΜΟ Ι Ø Συνδυασμοί των ν αντικειμένων ανά κ με επανάληψη είναι οι τρόποι με τους οποίους μπορούμε να επιλέξουμε κ το πλήθος αντικείμενα από ένα σύνολο ν αντικειμένων με επανάληψη. (Στη περίπτωση των συνδυασμών δεν μας ενδιαφέρει η διάταξη επιλογής ή τοποθέτησης των κ επιλεγόμενων αντικειμένων). Τους συνδυασμούς των ν αντικειμένων ανά κ με επανάληψη, τους συμβολίζουμε με ⎡ν ⎤ ⎡ν ⎤ ⎛ν + κ − 1 ⎞ CΕ (ν , κ ) ή ⎢ ⎥ και δίνεται από τη σχέση: CΕ (ν ,κ ) = ⎢ ⎥ = ⎜⎜ ⎟⎟. ⎣κ ⎦ ⎣κ ⎦ ⎝ κ ⎠ 1. 1 9 Π Α Ρ Α Δ Ε ΙΓ Μ Α ( Ε Π Α Ν Α Λ Η Π Τ Ι Κ Ο Ι Σ Υ Ν Δ Υ Α Σ Μ Ο Ι ) Ø Ρίχνουμε ταυτόχρονα 3 ίδια νομίσματα. Πόσα είναι τα δυνατά αποτελέσματα; Απάντηση: Κατά τη ρίψη νομίσματος, τα δυνατά αποτελέσματα είναι “K” (Κεφάλι) ή “Γ” (Γράμματα). Προφανώς κατά τη ρίψη τριών νομισμάτων, τα δυνατά αποτελέσματα είναι: ΚΚΚ, ΚΚΓ, ΚΓΓ και ΓΓΓ. (Δεν μας ενδιαφέρει η διάταξη των “K” και “Γ” διότι τα νομίσματα ρίχνονται ταυτόχρονα) Δηλαδή τα δυνατά αποτελέσματα είναι 4. Θα χρησιμοποιήσουμε τώρα τις επαναληπτικές διατάξεις για να λύσουμε το πρόβλημα. Τα δυνατά αποτελέσματα είναι όσοι οι συνδυασμοί με επανάληψη των ν = 2 αντικειμένων ανά κ = 3. Τα “αντικείμενα” που επιλέγουμε είναι “Κ” ή “Γ” και οι επαναλήψεις που μπορούμε να έχουμε είναι τρείς. Δηλαδή τα δυνατά αποτελέσματα είναι: -8 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ ⎡ 2⎤ ⎛ 2 + 3 − 1 ⎞ ⎛ 4 ⎞ 4! 4! CΕ ( 2 ,3 ) = ⎢ ⎥ = ⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ = = =4. 3 ⎣ ⎦ ⎝ 3 ⎠ ⎝ ⎠ 3 ( 4 − 3 )! 3! 3! 1. 2 0 Π Α Ρ Α Δ Ε Ι Γ Μ Α ( Ε Π Α Ν Α Λ Η Π Τ ΙΚ Ε Σ Μ Ε Τ Α Θ Ε Σ Ε ΙΣ ) Όταν λέμε “αναγραμματισμό” μιάς λέξης, εννοούμε μία καινούργια (όχι κατ ανάγκη με νόημα) λέξη που προκύπτει αν αλλάξουμε τη σειρά των γραμμάτων (αναδιατάξουμε τα γράμματα), της αρχικής λέξης. Ø Να βρεθεί το πλήθος των αναγραμματισμών της λέξης “ΘΑΛΑΣΣΑ”. Απάντηση 1 ος Τρόπος (Με Επαναλληπτικές Μεταθέσεις) Στη λέξη “ΘΑΛΑΣΣΑ” υπάρχει τρείς φορές το γράμμα “Α”, δύο φορές το γράμμα “Σ”, μία φορά το γράμμα “Θ” και μία φορά το γράμμα “Λ”. Άρα το πλήθος των αναγραμματισμών ισούται με τις επαναληπτικές διατάξεις των τεσσάρων ειδών αντικειμένων Α,Σ,Θ,Λ ( 4 γράμματα συμμετέχουν) με 3 , 2 , 1 , 1 πλήθος στοιχείων αντίστοιχα. ( 3 + 2 + 1 + 1 )! 7! Μ ( 3,2 ,1,1 ) = = = 420 3!⋅2!⋅1!⋅1! 3!⋅2!⋅1!⋅1! 2 ος Τρόπος (Με Συνδυασμούς και Πολλαπλασιαστική αρχή) Ας υποθέσουμε ότι διαθέτουμε μία θήκη με επτά θέσεις στις οποίες θα τοποθετήσουμε τα γράμματα Α, Α, Α, Σ, Σ, Θ, Λ ώστε να δημιουργούνται καινούργιες λέξεις (αναγραμματισμοί της αρχικής λέξης). ⎛7 ⎞ Τα τρία Α, Α, Α μπορούμε να τα τοποθετήσουμε στις επτά θέσεις με ⎜⎜ ⎟⎟ τρόπους. ⎝3⎠ ⎛4 ⎞ Τα δύο Σ, Σ μπορούμε να τα τοποθετήσουμε στις τέσερεις υπόλοιπες θέσεις με ⎜⎜ ⎟⎟ τρόπους. ⎝2⎠ ⎛ 2⎞ Το Θ μπορούμε να το τοποθετήσουμε στις δύο υπόλοιπες θέσεις με ⎜⎜ ⎟⎟ τρόπους. ⎝ 1⎠ ⎛ 1⎞ Το Λ τέλος μπορούμε να το τοποθετήσουμε στη μία θέση με ⎜⎜ ⎟⎟ = 1 τρόπους. ⎝ 1⎠ -9 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Άρα σύμφωνα με τη πολλαπλασιαστική αρχή υπάρχουν : ⎛ 7 ⎞ ⎛ 4 ⎞ ⎛ 2 ⎞ ⎛ 1⎞ ⎜⎜ ⎟⎟ ⋅ ⎜⎜ ⎟⎟ ⋅ ⎜⎜ ⎟⎟ ⋅ ⎜⎜ ⎟⎟ = 420 αναγραμματισμοί. ⎝ 3 ⎠ ⎝ 2 ⎠ ⎝ 1 ⎠ ⎝ 1⎠ 1. 2 1 Π Α Ρ Α Δ Ε Ι Γ Μ Α ( Ε Π Α Ν Α Λ Η Π Τ ΙΚ Ε Σ Μ Ε Τ Α Θ Ε Σ Ε ΙΣ ) Ø Να βρεθεί το άθροισμα όλων των πενταψήφιων θετικών ακέραιων που προκύπτουν από την αναδιάταξη των ψηφίων του αριθμού 12345”. Απάντηση Το πλήθος των αριθμών που έχουν τελευταίο ψηφίο τη μονάδα ( 1 ) είναι: 4! = 24. (όσες είναι δηλαδή οι μεταθέσεις των τεσσάρων αριθμών που βρίσκονται στις τέσσερεις πρώτες θέσεις) Υπάρχουν λοιπόν 4! = 24 αριθμοί που τελειώνουν σε 1 , 4! = 24 αριθμοί που τελειώνουν σε 2 , 4! = 24 αριθμοί που τελειώνουν σε 3 , 4! = 24 αριθμοί που τελειώνουν σε 4 και 4! = 24 αριθμοί που τελειώνουν σε 5. Άρα το άθροισμα των μονάδων όλων των αριθμών που δημιουργούνται, είναι: 5 ⋅6 24( 1 + 2 + 3 + 4 + 5 ) = 24 = 24 ⋅ 15 = 360. 2 Με ανάλογο τρόπο σκεπτόμενοι, συμπεραίνουμε ότι το άθροισμα των δεκάδων όλων των αριθμών που δημιουργούνται, είναι: 5 ⋅6 24( 1 + 2 + 3 + 4 + 5 ) ⋅ 10 = 24 ⋅ 10 = 24 ⋅ 15 ⋅ 10 = 3600. 2 Με όμοιο τρόπο σκεπτόμενοι (για τις εκατοντάδες, τις χιλιάδες κ.λ.π), διαπιστώνουμε ότι το άθροισμα όλων αριθμών είναι: 360( 1 + 10 + 100 + 1000 + 10000 ) = 360 ⋅ 11111. 1. 2 2 Π Ρ ΟΒ Λ Η ΜΑ Ø Με πόσους τρόπους μπορούμε να τοποθετήσουμε στη σειρά (τη μία δίπλα στην άλλη) τρείς τελείως ίδιες μαύρες και πέντε τελείως ίδιες άσπρες σφαίρες. Λύση Έστω ότι διαθέτουμε μία θήκη με οκτώ θέσεις (τη μία δίπλα στην άλλη) στην οποία θα τοποθετήσουμε τις σφαίρες. ⎛ 8 ⎞ 8! Οι τρεις μαύρες σφαίρες μπορούν να τοποθετηθούν με ⎜⎜ ⎟⎟ = = 56 τρόπους στις 8 θέσεις της ⎝ 3 ⎠ 5!3! θήκης. Οι πέντε λευκές σφαίρες στη συνέχεια, μπορούν να τοποθετηθούν με ένα μόνο τρόπο στις πέντε κενές θέσεις της θήκης. Άρα υπάρχουν συνολικά 56 τρόποι τοποθέτησης των σφαιρών. Παρατηρήσεις 1. Η “ιδιορυθμία” του προβλήματος βρίσκεται στο γεγονός ότι: η αντιμετάθεση δύο σφαιρών του ιδίου χρώματος, δεν αποτελεί διαφορετική συνολική τοποθέτηση των σφαιρών. - 10 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 2. Αν τοποθετήσουμε πρώτα τις λευκές σφαίρες τότε οι δυνατοί τρόποι τοποθέτησης είναι ⎛ 8 ⎞ 8! ⎜⎜ ⎟⎟ = = 56. Προφανώς το αποτέλεσμα είναι το ίδιο. ⎝ 5 ⎠ 5!3! ⎛ n + k ⎞ ⎛ n + k ⎞ ( n + k )! 3. Γενικότερα ισχύει η ισότητα ⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ =. ⎝ n ⎠ ⎝ k ⎠ n! k! 4. Ανάλογους τρόπους σκέψεις εφαρμόζουμε και στους αναγραμματισμούς των λέξεων. 1. 2 3 Π Ρ ΟΒ Λ Η ΜΑ Ø Με πόσους τρόπους μπορούμε να τοποθετήσουμε στη σειρά (τη μία δίπλα στην άλλη) τρείς τελείως ίδιες μαύρες, πέντε τελείως ίδιες άσπρες σφαίρες και επτά τελείως ίδιες κόκινες σφαίρες; Λύση Έστω ότι διαθέτουμε μία θήκη με δεκαπέντε θέσεις (τη μία δίπλα στην άλλη) στην οποία θα τοποθετήσουμε τις σφαίρες. Οι 3 μαύρες σφαίρες μπορούν να τοποθετηθούν με ⎛ 15 ⎞ 15! 13 ⋅ 14 ⋅ 15 ⎜⎜ ⎟⎟ = = = 5 ⋅ 7 ⋅ 13 = 455 ⎝ 3 ⎠ 12!3! 1⋅ 2 ⋅ 3 τρόπους στις 15 θέσεις της θήκης. Οι 5 λευκές σφαίρες στη συνέχεια, μπορούν να τοποθετηθούν με ⎛ 12 ⎞ 12! 8 ⋅ 9 ⋅ 10 ⋅ 11 ⋅ 12 ⎜⎜ ⎟⎟ = = = 8 ⋅ 9 ⋅ 11 = 792 ⎝ 5 ⎠ 7 !5! 1⋅ 2 ⋅ 3⋅ 4 ⋅ 5 τρόπους στις 12 κενές θέσεις της θήκης. Οι 7 (τέλος) κόκινες σφαίρες μπορούν να τοποθετηθούν με ένα μόνο τρόπο στις υπόλοιπες επτά κενές θέσεις της θήκης. ⎛ 15 ⎞ ⎛ 12 ⎞ Άρα υπάρχουν συνολικά ⎜⎜ ⎟⎟ ⋅ ⎜⎜ ⎟⎟ = 455 ⋅ 792 = 360360 τρόποι τοποθέτησης των σφαιρών. ⎝3⎠ ⎝5⎠ Παρατηρήσεις 1. Το πρόβλημα αυτό αποτελεί “μερική γενίκευση” του προηγούμενου προβλήματος. 2. Για τον υπολογισμό των τρόπων τοποθέτησης, μπορούμε να χρησιμοποιήσουμε τον τύπο των επαναληπτικών μεταθέσεων. ( 3 + 5 + 7 )! 15! 8 ⋅ 9 ⋅ 10 ⋅ 11 ⋅ 12 ⋅ 13 ⋅ 14 ⋅ 15 M ( 3,5 ,7 ) = = = = 360360 3!5!7 ! 3!5!7 ! ( 1⋅ 2 ⋅ 3 ) ⋅ ( 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ) - 11 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 1. 2 4 Π Ρ ΟΒ Λ Η ΜΑ Ø Με πόσους τρόπους μπορoύν να καθίσουν έντεκα θεατές στις είκοσι συνεχόμενες θέσεις ενός θεάτρου; Λύση Ο 1 ος θεατής μπορεί να καθίσει με 20 τρόπους Ο 2 ος θεατής μπορεί να καθίσει με 19 τρόπους Ο 3 ος θεατής μπορεί να καθίσει με 18 τρόπους................................... Ο 11 ος θεατής μπορεί να καθίσει με 10 τρόπους Άρα (σύμφωνα με τη πολλαπλασιαστική αρχή) οι δυνατοί τρόποι είναι: 20! 20 ⋅ 19 ⋅ 18 ⋅ ⋅ 11 ⋅ 10 =. ( 20 − 11 )! (Διατάξεις 20 αντικειμένων ανά 11) 1. 2 5 Π Ρ ΟΒ Λ Η ΜΑ Ø Με πόσους τρόπους μπορoύν να καθίσουν έντεκα θεατές στις είκοσι συνεχόμενες θέσεις ενός θεάτρου, αν τρία συγκεκριμένα άτομα καθίσουν σε διαδοχικές θέσεις (ο ένας δίπλα στον άλλο); Λύση Τα τρία συγκεκριμένα άτομα (επειδή θα καθίσει ο ένας δίπλα στον άλλο) μπορούν να καταλάβουν τις τρεις συνεχόμενες θέσεις 1,2,3 ή 2,3,4 ή....ή 18,19,20. Δηλαδή υπάρχουν 18 τρόποι κατάληψης των τριών διαδοχικών θέσεων. Για κάθε ένα από τους παραπάνω τρόπους, υπάρχουν 3!= 6 τρόποι αντιμετάθεσης των τριών συγκεκριμένων ατόμων μεταξύ τους. Άρα ολοι οι δυνατοί τρόποι με τους οποίους μπορούν να καθίσουν τα τρία άτομα είναι: 6 ⋅ 18 = 108. Οι υπόλοιποι 8 θεατές μπορούν να καθίσουν στις 17 θέσεις με 17! 17! = = 17 ⋅ 16 ⋅ 15 ⋅ 14 ⋅ 13 ⋅ 12 ⋅ 11 ⋅ 10 τρόπους. ( 17 − 8 )! 9! Άρα όλοι οι δυνατοί τρόποι είναι 17 ⋅ 16 ⋅ 15 ⋅ 14 ⋅ 13 ⋅ 12 ⋅ 11 ⋅ 10 ⋅ 108. 1. 2 6 Π Ρ ΟΒ Λ Η ΜΑ Ø Σε μία τάξη φοιτούν 12 αγόρια και 10 κορίτσια. Πόσες πενταμελείς επιτροπές (από παιδιά της τάξης) μπορούν να δημιουργηθούν, αν: 1. Δεν υπάρχει κανένας περιορισμός. 2. Στην επιτροπή συμμετέχουν 3 τουλάχιστον κορίτσια. Λύση 1. Όλα τα παιδιά της τάξης είναι 12 + 10 = 22. Η τελική σύνθεση της επιτροπής, δεν επηρεάζεται από τη σειρά με την οποία επιλέγουμε τα παιδιά. Προφανώς οι επιτροπές “ΜΑΡΙΑ, ΓΙΩΡΓΟΣ, ΝΙΚΟΣ, ΔΗΜΗΤΡΑ, ΣΤΕΛΛΑ”, “ΓΙΩΡΓΟΣ, ΜΑΡΙΑ, ΝΙΚΟΣ, ΔΗΜΗΤΡΑ, ΣΤΕΛΛΑ” και “ ΜΑΡΙΑ, ΓΙΩΡΓΟΣ, ΣΤΕΛΛΑ, ΝΙΚΟΣ, ΔΗΜΗΤΡΑ ”, είναι ίδιες. Άρα οι πενταμελείς επιτροπές που μπορούν να δημιουργηθούν είναι όσοι οι συνδυασμοί των 22 παιδιών ανά 5. Δηλαδή : ⎛ 22 ⎞ 22! 22! 18 ⋅ 19 ⋅ 20 ⋅ 21 ⋅ 22 ⎜⎜ ⎟⎟ = = = = 3 ⋅ 19 ⋅ 21 ⋅ 22 = 26334. ⎝ 5 ⎠ ( 22 − 5 )!5! 17!5! 1⋅ 2 ⋅ 3 ⋅ 4 ⋅5 - 12 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 2. Το πλήθος των επιτροπών στις οποίες συμμετέχουν τρία κορίτσια ισούται με το άθροισμα του πλήθους των επιτροπών που περιέχουν τρία ή τέσσερα ή πέντε κορίτσια. ⎛ 10 ⎞ Τα τρία κορίτσια που θα συμμετάσχουν στην επιτροπή, μπορούμε να τα επιλέξουμε με ⎜⎜ ⎟⎟ ⎝3⎠ ⎛ 12 ⎞ τρόπους. Ταυτόχρονα μπορούμε να επιλέξουμε με ⎜⎜ ⎟⎟ τρόπους τα δύο αγόρια, ώστε να ⎝2⎠ συμπληρωθούν τα πέντε μέλη της επιτροπής. Άρα δημιουργούνται ⎛ 10 ⎞ ⎛ 12 ⎞ 10! 12! 12! 8 ⋅ 9 ⋅ 10 ⋅ 11 ⋅ 12 ⎜⎜ ⎟⎟ ⋅ ⎜⎜ ⎟⎟ = ⋅ = = = 8 ⋅ 9 ⋅ 10 ⋅ 11 = 7920 ⎝ 3 ⎠ ⎝ 2 ⎠ 7 !3! 10!2! 2!3!7! 1⋅ 2 ⋅1⋅ 2 ⋅ 3 επιτροπές στις οποίες συμμετέχουν τρία κορίτσια. Με ανάλογο τρόπο διαπιστώνουμε ότι δημιουργούνται ⎛ 10 ⎞ ⎛ 12 ⎞ 10! 12! 12 ⋅ 10! 12 ⋅ 10 ⋅ 9 ⋅ 8 ⋅ 7 ⎜⎜ ⎟⎟ ⋅ ⎜⎜ ⎟⎟ = ⋅ = = = 10 ⋅ 9 ⋅ 7 ⋅ 4 = 2520 ⎝ 4 ⎠ ⎝ 1 ⎠ 6 !4! 11!1! 4!6! 1⋅ 2 ⋅3 ⋅4 επιτροπές στις οποίες συμμετέχουν τέσσερα κορίτσια. Τέλος δημιουργούνται ⎛ 10 ⎞ 10! 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⎜⎜ ⎟⎟ = = = 9 ⋅ 7 ⋅ 4 = 252 ⎝ 5 ⎠ 5!5! 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 επιτροπές στις οποίες συμμετέχουν πέντε κορίτσια. Άρα μπορούν να δημιουργηθούν 7920 + 2520 + 252 = 10692 επιτροπές στις οποίες συμμετέχουν τρία τουλάχιστον κορίτσια. 1. 2 7 Π Ρ Ο Β Λ Η ΜΑ ( Κ Υ Κ Λ Ι Κ Ε Σ ΜΕ ΤΑ Θ Ε Σ Ε Ι Σ ) Ø Με πόσους τρόπους μπορoύν να καθίσουν τέσσερα άτομα γύρω από ένα κυκλικό τραπέζι; Λύση Συμβολίζουμε με A, B, C, D τα άτομα που θα καθίσουν γύρω από το τραπέζι. Στο σχήμα (για εποπτικούς λόγους) συμβολίζουμε τα άτομα με σημεία. Αν υποθέσουμε ότι τα τέσσερα άτομα τα τοποθετούμε στη σειρά (το ένα δίπλα στο άλλο), τότε στις τέσσερεις παρακάτω τοποθετήσεις (μεταθέσεις) των ατόμων: ABCD, BCDA, CDAB και DABC αντιστοιχεί μία και μόνο τοποθέτησή τους γύρω από το τραπέζι. - 13 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Αντίστροφα, σε κάθε τοποθέτηση των ατόμων γύρω από το τραπέζι, αντιστοιχούν τέσσερεις μεταθέσεις των ατόμων (αν τους τοποθετούσαμε στη σειρά) που προκύπτουν ως εξής: Ξεκινάμε από κάθε άτομο (που κάθεται στο τραπέζι) και κινούμενοι δεξιόστροφα καταγράφουμε (σε σειρά) αυτούς που συναντάμε στο τραπέζι. Συμπεραίνουμε λοιπόν ότι το πλήθος των μεταθέσεων των τεσσάρων ατόμων, είναι τετραπλάσιο από το πλήθος των τρόπων που θα καθίσουν γύρω από το τραπέζι. 4! Άρα όλοι οι δυνατοί τρόποι που θα καθίσουν γύρω από το τραπέζι είναι: = 3! = 6. 4 Στο παρακάτω σχήμα φαίνονται όλοι οι δυνατοί τρόποι τοποθέτησης γύρω από το κυκλικό τραπέζι. 1. 2 8 Π Ρ ΟΒ Λ Η ΜΑ Ø Με πόσους τρόπους μπορούμε να μοιράσουμε 10 πορτοκάλια, 15 μήλα και 20 αχλάδια σε δύο παιδιά, αν: 1. Δεν υπάρχει κανένας περιορισμός. 2. Κάθε παιδί πρέπει να πάρει 3 τουλάχιστον πορτοκάλια, 2 τουλάχιστον μήλα και 4 τουλάχιστον αχλάδια. Λύση Όλα τα φρούτα θα μοιραστούν στα δύο παιδιά. Αν λοιπόν το πρώτο παιδί πάρει 4 πορτοκάλια, τότε το δεύτερο θα πάρει “αναγκαστικά” 6 πορτοκάλια. Δηλαδή σημαντικό ρόλο παίζει η κατανομή των φρούτων στο ένα από τα δύο παιδιά (διότι το άλλο θα πάρει τα υπόλοιπα). 1. Το ένα από τα δύο παιδιά μπορεί να πάρει 0 ή 1 ή 2 ή... ή 10 πορτοκάλια. Άρα οι τρόποι με τους οποίους μπορούμε να μοιράσουμε τα πορτοκάλια είναι: ( 10 + 1 ) = 11. Με όμοιο τρόπο βρίσκουμε ότι τα μήλα μπορούν να μοιραστούν με ( 15 + 1 ) = 16 και τα αχλάδια με ( 20 + 1 ) = 21 τρόπους. Άρα τα φρούτα μπορούν να μοιραστούν με ( 10 + 1 )( 15 + 1 )( 20 + 1 ) = 11 ⋅ 16 ⋅ 21 = 3696 τρόπους. 2. Το ένα από τα δύο παιδιά μπορεί να πάρει 3 ή 4 ή 5 ή... ή 7 πορτοκάλια. Άρα οι τρόποι με τους οποίους μπορούμε να μοιράσουμε τα πορτοκάλια είναι: 7 − 3 + 1 = ( 10 − 3 ) − 3 + 1 = 10 − 2 ⋅ 3 + 1 = 5. Το ένα από τα δύο παιδιά μπορεί να πάρει 2 ή 3 ή 4 ή... ή 13 μήλα. Άρα οι τρόποι με τους οποίους μπορούμε να μοιράσουμε τα μήλα είναι: 13 − 2 + 1 = ( 15 − 2 ) − 2 + 1 = 15 − 2 ⋅ 2 + 1 = 12. Το ένα από τα δύο παιδιά μπορεί να πάρει 4 ή 5 ή 6 ή... ή 16 αχλάδια. Άρα οι τρόποι με τους οποίους μπορούμε να μοιράσουμε τα αχλάδια είναι: 16 − 4 + 1 = ( 20 − 4 ) − 4 + 1 = 20 − 2 ⋅ 4 + 1 = 13. - 14 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Τελικά όλοι οι δυνατοί τρόποι μοιράσματος των φρούτων είναι: ( 10 − 2 ⋅ 3 + 1 )( 15 − 2 ⋅ 2 + 1 )( 20 − 2 ⋅ 4 + 1 ) = 5 ⋅ 12 ⋅ 13 = 780. 1. 2 9 Π Ρ ΟΒ Λ Η ΜΑ Ø Να βρεθεί το πλήθος των διαιρετών του αριθμού 600. Λύση 1 ος Τρόπος Ο αριθμός 600 (αναλυόμενος σε γινόμενο πρώτων παραγόντων) γράφεται: 600 = 2 3 ⋅ 3 ⋅ 5 2 = 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ 5 ⋅ 5. Υποθέτουμε ότι έχουμε τρεις διαφορετικές μεταξύ τους κάρτες που έχουν γραμμένο επάνω τους τον αριθμό 2 , μία κάρτα που έχει γραμμένο τον αριθμό 3 και δύο διαφορετικές μεταξύ τους κάρτες που έχουν γραμμένο τον αριθμό 5. Μοιράζουμε όλες τις κάρτες σε δύο παιδιά και τους ζητάμε να γράψουν το γινόμενο των αριθμών που έχουν επάνω τους οι κάρτες με τη βοήθεια δυνάμεων του 2 , του 3 του 5 και το τελικό αποτέλεσμα. Αν (δηλαδή) σε ένα παιδί δοθούν δύο κάρτες με τους αριθμούς 2 και μία κάρτα με τον αριθμό 5 τότε αυτό θα πρέπει να γράψει ότι έχει τον αριθμό: 2 2 ⋅ 30 ⋅ 5 1 = 20. Το δεύτερο παιδί αναγκαστικά θα έχει τον αριθμό 21 ⋅ 31 ⋅ 51 = 30. Παρατηρούμε λοιπόν ότι στα χέρια των παιδιών δημιουργούνται δύο αριθμοί που το γινόμενό τους είναι 600 , οπότε οι αριθμοί αυτοί θα είναι διαιρέτες του 600. Από τη τελευταία παρατήρηση συμπεραίνουμε ότι το πλήθος των διαιρετών του 600 , ταυτίζεται με το πλήθος των τρόπων με τους οποίους μπορούμε να μοιράσουμε τις έξι κάρτες στα παιδιά. Σκεφτόμενοι με τον τρόπο του προηγούμενου προβλήματος, καταλήγουμε ότι το πλήθος των διαιρετών του 600 είναι: ( 3 + 1 )( 1 + 1 )( 2 + 1 ) = 24. 2 ος Τρόπος Ο αριθμός 600 (αναλυόμενος σε γινόμενο πρώτων παραγόντων) γράφεται: 600 = 23 ⋅ 3 ⋅ 52. Κάθε διαιρέτης του 600 είναι της μορφής 2 k ⋅ 3m ⋅ 5 n , όπου k , m ,n είναι ακέραιοι με 0 ≤ k ≤ 3 , 0 ≤ m ≤ 1 και 0 ≤ n ≤ 2. Το πλήθος λοιπόν των διαιρετών ταυτίζεται με το πλήθος επιλογής των εκθετών k , m ,n στην παράσταση 2 k ⋅ 3m ⋅ 5 n. Το k μπορούμε να το επιλέξουμε με 4 τρόπους, το m με 2 τρόπους και το n με 3 τρόπους. Άρα τις τριάδες των εκθετών μπορούμε να τις επιλέξουμε με 4 ⋅ 2 ⋅ 3 = 24 τρόπους. Παρατήρηση 1. Γενικότερα το πλήθος των διαιρετών του θετικού ακέραιου a = p1n p2n p3n 1 2 3 pknk είναι: ( n1 + 1 )( n2 + 1 ) ( nk + 1 ). 2. Αν a = 2 τότε διαιρέτες του είναι οι αριθμοί 20 ,21 ,22 ,23 ,24 και το άθροισμά τους είναι: 4 25 − 1 r( a ) = 1 + 21 + 22 + 23 + 24 = = 31. 2 −1 Αν a = 24 ⋅ 3 τότε, επί πλέον διαιρέτες του αριθμού a (εκτός από τους 1,2 ,2 2 ,23 ,2 4 ) είναι και οι αριθμοί 3 ⋅ 1, 3 ⋅ 2 , 3 ⋅ 2 2 , 3 ⋅ 2 3 , 3 ⋅ 2 4. Εκτελούμε τις πράξεις μεταξύ των παρενθέσεων ( 1 + 2 + 22 + 23 + 24 ) και ( 1 + 3 ) έχουμε: - 15 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ ( 1 + 2 + 22 + 23 + 24 ) ( 1 + 3 ) = 1 + 2 + 22 + 23 + 24 + 3 ⋅ 1 + 3 ⋅ 2 + 3 ⋅ 22 + 3 ⋅ 23 + 3 ⋅ 24. Παρατηρούμε ότι κάθε όρος του αθροίσματος είναι διαιρέτης του αριθμού a = 24 ⋅ 3. 25 − 1 32 − 1 Το άθροισμα λοιπόν των διαιρετών θα είναι: ⋅ = 124. 2 − 1 3 −1 3. Γενικότερα το άθροισμα των διαιρετών του θετικού ακέραιου a = p1n p2n p3n pkn είναι: 1 2 3 k p1n1 +1 −1 p2n2 +1 −1 pknk +1 −1 ⋅ ⋅ ⋅. p1 − 1 p2 − 1 pk − 1 - 16 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 2 Σ Υ Ν Θ ΕΤ Α Π Ρ Ο Β Λ Η Μ Α Τ Α 2. 1 Π Ρ ΟΒ Λ Η ΜΑ Ø Δέκα άτομα βρίσκονται στον ανελκυστήρα (ασανσέρ) ενός επταόροφου κτιρίου. Ο ανελυστήρας ξεκινά από το ισόγειο και όλοι οι επιβάτες αποβιβάζονται σε κάποιο όροφο. Με πόσους τρόπους μπορεί να γίνει η αποβίβαση των επιβατών στους επτά ορόφους, αν στο πρώτο όροφο αποβιβαστούν δύο ακριβώς άτομα; Απάντηση Η επιλογή των 2 ατόμων (που θα αποβιβαστούν στο πρώτο όροφο), μπορεί να γίνει με ⎛ 10 ⎞ 10! ⎜⎜ ⎟⎟ = τρόπους. ⎝ 2 ⎠ 8! 2! Για κάθε ένα από τους παραπάνω τρόπους, οι υπόλοιποι 8 επιβάτες μπορούν να αποβιβαστούν στους 6 ορόφους με 6 8 τρόπους. (♦ ) Άρα (σύμφωνα με τη πολλαπλασιαστική αρχή) όλοι οι δυνατοί τρόποι αποβίβασης των επιβατών ⎛ 10 ⎞ στους επτά οπόφους είναι: ⎜⎜ ⎟⎟ ⋅ 6 8. ⎝2⎠ (♦) Το 1 ο άτομο μπορεί να αποβιβαστεί με 6 τρόπους. Το 2 ο άτομο μπορεί να αποβιβαστεί με 6 τρόπους....... Το 8 ο άτομο μπορεί να αποβιβαστεί με 6 τρόπους. Επαναληπτικές Διατάξεις έξι ανά οκτώ Ε ( 6 ,8 ) = 6 8. 2. 2 Π Ρ Ο Β ΛΗ ΜΑ Ø Επάνω στη περιφέρεια ενός κύκλου δίνονται επτά διαφορετικά μεταξύ τους σημεία. Βρείτε: (α) Πόσα ευθύγραμμα τμήματα ορίζονται με άκρα τα επτά αυτά σημεία; (β) Πόσα τρίγωνα ορίζονται με κορυφές τα επτά αυτά σημεία; (γ) Πόσες διαγώνιες έχει το δημιουργούμενο κυρτό επτάγωνο; Απάντηση Με δεδομένο ότι δύο διαφορετικά σημεία ορίζουν ένα ευθύγραμμο τμήμα, το πλήθος των ευθυγράμμων τμημάτων που δημιουργούνται ισούται με το πλήθος των συνδυασμών των επτά σημείων (αντικειμένων) ανά δύο. ⎛7 ⎞ 7! 7! 6 ⋅7 C( 7 ,2 ) = ⎜⎜ ⎟⎟ = = = = 21. ⎝ 2 ⎠ ( 7 − 2 )!2! 5!2! 1 ⋅ 2 Με ανάλογες σκέψεις καταλήγουμε ότι το πλήθος των τριγώνων που δημιουργούνται είναι όσοι οι συνδυασμοί των επτά σημείων (αντικειμένων) ανά τρία. ⎛7 ⎞ 7! 7! 5 ⋅ 6 ⋅7 C( 7 ,3 ) = ⎜⎜ ⎟⎟ = = = = 35. ⎝ ⎠ ( 7 − 3 )!3! 4!3! 1 ⋅ 2 ⋅ 3 3 Το πλήθος των διαγωνίων προκύπτει από το πλήθος όλων των ευθυγράμμων τμημάτων αφαιρώντας τα επτά ευθύγραμμα τμήματα που αποτελούν τις πλευρές του πολυγώνου. Δηλαδή το πλήθος των διαγωνίων είναι 21 − 7 = 14. 2. 3 Π Ρ Ο Β Λ Η Μ Α ( ΤΡ Ι Γ Ω Ν Ι Κ Ο Π Λ Ε Γ Μ Α ) Ø Ισόπλευρο τρίγωνο πλευράς μήκους 5 , το χωρίζουμε με ευθείες παράλληλες προς τις πλευρές του σε 25 ισόπλευρα τρίγωνα πλευράς μήκους 1 (όπως φαίνεται στο διπλανό σχήμα). - 17 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Πόσα συνολικά ισόπλευρα τρίγωνα (που οι πλευρές τους είναι παράλληλες με τις πλευρές του αρχικού τριγώνου) ορίζονται (δημιουργούνται) μετά από αυτό το χωρισμό; Λύση Σε κάθε πλευρά του τριγώνου θεωρούμε 4 σημεία που (μαζί με τις κορυφές του), τις χωρίζουν σε πέντε ίσα ευθύγραμμα τμήματα. Τα παράλληλα προς τις πλευρές ευθύγραμμα τμήματα τέμνονται σε 6 σημεία (που βρίσκονται στο εσωτερικό του μεγάλου ισόπλευρου τριγώνου). Έτσι στο δημιουργούμενο σχηματισμό (που ονομάζεται και “κανονικό τριγωνικό πλέγμα”) έχουμε 21 σημεία, που θα αποτελέσουν τις κορυφές των τριγώνων. Γνωρίζουμε ότι σε κάθε ισόπλευρο τρίγωνο, το ορθόκεντρο, το περίκεντρο, το βαρύκεντρο και το έκκεντρο ταυτίζονται. Το περίκεντρο του ισοπλεύρου τριγώνου, θα το ονομάζουμε κέντρο του τριγώνου. Τα κέντρα των τριγώνων που έχουν τον ίδιο προσανατολισμό με το αρχικό τρίγωνο θα τα σημειώνουμε με “▲”. Τα κέντρα των τριγώνων που έχουν αντίθετο προσανατολισμό με το αρχικό τρίγωνο θα τα σημειώνουμε με “▼”. Με κορυφές τα σημεία του “πλέγματος” παρατηρούμε ότι δημιουργούνται: 1. Τρίγωνα τύπου T1 (που η πλευρά τους έχει μήκος 1 ) και ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου. 5⋅6 Το πλήθος των τριγώνων τύπου T1 είναι S1 = 1 + 2 + 3 + 4 + 5 = = 15. 2 Τρίγωνα τύπου T1′ (που η πλευρά τους έχει μήκος 1 ) και ο προσανατολισμός τους είναι αντίθετος με το προσανατολισμό του αρχικού τριγώνου. 4⋅5 Το πλήθος των τριγώνων τύπου T1′ είναι S1′ = 1 + 2 + 3 + 4 = = 10. 2 2. Τρίγωνα τύπου T2 (που η πλευρά τους έχει μήκος 2 ) και ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου. 4 ⋅5 Το πλήθος των τριγώνων τύπου T2 είναι S 2 = 1 + 2 + 3 + 4 = = 10. 2 - 18 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Τρίγωνα τύπου T2′ (που η πλευρά τους έχει μήκος 2 ) και ο προσανατολισμός τους είναι αντίθετος με το προσανατολισμό του αρχικού τριγώνου. 2⋅3 Το πλήθος των τριγώνων τύπου T2′ είναι S 2′ = 1 + 2 = = 3. 2 3. Τρίγωνα τύπου T3 (που η πλευρά τους έχει μήκος 3 ) και ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου. 3⋅4 Το πλήθος των τριγώνων τύπου T3 είναι S3 = 1 + 2 + 3 = =6. 2 4. Τρίγωνα τύπου T4 (που η πλευρά τους έχει μήκος 4 ) και ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου. 2⋅3 Το πλήθος των τριγώνων τύπου T4 είναι S4 = 1 + 2 = = 3. 2 Τέλος “δημιουργείται” το τρίγωνο τύπου T5 (που η πλευρά του έχει μήκος 5 ) και είναι ουσιαστικά το μεγάλο αρχικό ισόπλευρο τρίγωνο. Τελικά το πλήθος των τριγώνων είναι: S = S1 + S2 + S3 + S 4 + S 5 + S1′ + S 2′ + S3′ = 15 + 10 + 6 + 3 + 1 + 10 + 3 = 48. 2. 4 Π Ρ Ο Β Λ Η Μ Α ( Γ Ε Ν Ι Κ Ε Υ Σ Η Τ Ρ Ι Γ Ω Ν ΙΚ Ο Υ Π Λ Ε Γ Μ Α ΤΟ Σ ) - 19 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Ø Ισόπλευρο τρίγωνο πλευράς μήκους n (όπου n θετικός ακέραιος), το χωρίζουμε με ευθείες παράλληλες προς τις πλευρές του σε n2 τρίγωνα πλευράς μήκους 1 (όπως φαίνεται στο διπλανό σχήμα, για n = 5 ). Πόσα συνολικά ισόπλευρα τρίγωνα (που οι πλευρές τους είναι παράλληλες με τις πλευρές του αρχικού τριγώνου) ορίζονται (δημιουργούνται) μετά από αυτό το χωρισμό; Λύση Σε κάθε πλευρά του τριγώνου θεωρούμε n − 1 σημεία που (μαζί με τις κορυφές του), τις χωρίζουν σε n ίσα ευθύγραμμα τμήματα. Τα παράλληλα προς τις πλευρές ευθύγραμμα τμήματα τέμνονται ( n − 2 )( n − 1 ) σε 1 + 2 + 3 + + ( n − 2 ) = σημεία. Έτσι στο δημιουργούμενο σχηματισμό (που 2 ( n + 1 )( n + 2 ) ονομάζεται και “κανονικό τριγωνικό πλέγμα”) έχουμε 1 + 2 + 3 + + ( n + 1) = 2 σημεία, που θα αποτελέσουν τις κορυφές των τριγώνων. Με κορυφές τα σημεία του “πλέγματος” παρατηρούμε ότι δημιουργούνται: Τρίγωνα τύπου T1 (που η πλευρά τους έχει μήκος 1 ) και ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου. Το πλήθος των τριγώνων τύπου T1 είναι: n( n + 1 ) S1 = 1 + 2 + 3 + + n =. 2 Τρίγωνα τύπου T2 (που η πλευρά τους έχει μήκος 2 ) και ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου. Το πλήθος των τριγώνων τύπου T2 είναι: ( n − 1 )n S2 = 1 + 2 + 3 + + ( n − 1 ) =. 2 Τρίγωνα τύπου T3 (που η πλευρά τους έχει μήκος 3 ) και ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου. Το πλήθος των τριγώνων τύπου T3 είναι: ( n − 2 )( n − 1 ) S3 = 1 + 2 + 3 + + ( n − 2 ) =. 2....................... Τρίγωνα τύπου Tn −2 (που η πλευρά τους έχει μήκος n − 2 ) και ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου. Το πλήθος των τριγώνων τύπου Tn − 2 είναι: 3⋅4 Sn − 2 = 1 + 2 + 3 = =6. 2 Τρίγωνα τύπου Tn−1 (που η πλευρά τους έχει μήκος n − 1 ) και ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου. Το πλήθος των τριγώνων τύπου Tn −1 είναι: - 20 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 2⋅3 Sn − 1 = 1 + 2 = =3. 2 Τέλος “δημιουργείται” το τρίγωνο τύπου Tn (που η πλευρά του έχει μήκος n ) και ταυτίζεται ουσιαστικά το μεγάλο αρχικό ισόπλευρο τρίγωνο. Τελικά το πλήθος των τριγώνων που ο προσανατολισμός τους ταυτίζεται με το προσανατολισμό του αρχικού τριγώνου είναι: S = S n + S n − 1 + Sn − 2 + + S 3 + S 2 + S1 = 1⋅ 2 2 ⋅ 3 3 ⋅ 4 ( n − 2 )⋅( n − 1) ( n − 1)⋅ n = + + + + + + n2 = 2 2 2 2 2 ( n − 1)⋅ n ⋅( n + 1) = + n2. 6 Στη συνέχεια θα υπολογίσουμε το πλήθος των τριγώνων που ο προσανατολισμός τους είναι αντίθετος με τον προσανατολισμο του αρχικού τριγώνου. Με κορυφές τα σημεία του “πλέγματος” παρατηρούμε ότι δημιουργούνται: Τρίγωνα τύπου T1′ (που η πλευρά τους έχει μήκος 1 ) και ο προσανατολισμός τους είναι αντίθετος με το προσανατολισμό του αρχικού τριγώνου. Το πλήθος των τριγώνων τύπου T1′ είναι: ( n − 1 )n S1′ = 1 + 2 + + ( n − 1 ) =. 2 Τρίγωνα τύπου T2′ (που η πλευρά τους έχει μήκος 2 ) και ο προσανατολισμός τους είναι αντίθετος με το προσανατολισμό του αρχικού τριγώνου. Το πλήθος των τριγώνων τύπου T2′ είναι: ( n − 3 )( n − 2 ) S2′ = 1 + 2 + + ( n − 3 ) =. 2..................... Τέλος δημιουργούνται τρίγωνα τύπου Tk′ (που η πλευρά τους έχει μήκος k ) και ο προσανατολισμός τους είναι αντίθετος με το προσανατολισμό του αρχικού τριγώνου. Το πλήθος των τριγώνων τύπου Tk′ είναι: ( n − 2k + 1 )( n − 2 k + 2 ) Sk′ = 1 + 2 + + ( n − 2k + 1 ) =. 2 Όπου n = 2 k ή n = 2 k + 1. - 21 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 2. 5 Β ΑΛΚ ΑΝ Ι Κ Η Μ ΑΘ Η Μ Α Τ Ι Κ Η Ο ΛΥ Μ Π Ι Α Δ Α ΝΕ ΩΝ 2 0 1 1 Ø Δίνεται ισόπλευρο τρίγωνο ABC του οποίου κάθε πλευρά υποθέτουμε ότι έχει μήκος k > 0. Σε κάθε πλευρά του τριγώνου θεωρούμε n − 1 σημεία που την χωρίζουν σε n ίσα τμήματα. Ενώνουμε τα n − 1 σημεία της μίας πλευράς με τα n − 1 σημεία της άλλης πλευράς έτσι ώστε τα ευθύγραμμα τμήματα που δημιουργούνται να είναι παράλληλα με τη τρίτη πλευρά του τριγώνου. Με αυτό τον τρόπο, το αρχικό ισόπλευρο τρίγωνο ABC , χωρίζεται σε n 2 (μικρότερα) ισόπλευρα τρίγωνα των οποίων κάθε k πλευρά έχει μήκος. Το διπλανό σχήμα είναι ένα παράδειγμα για n n = 4. Θεωρούμε τώρα το σημειοσύνολο S που αποτελείται από τις κορυφές του τριγώνου ABC , από τα n − 1 σημεία που έχουμε θεωρήσει επάνω σε κάθε πλευρά και από τα σημεία που τέμνονται τα ευθύγραμμα τμήματα. Με κορυφές τα σημεία του σημειοσυνόλου S , δημιουργούνται k ρόμβοι τύπου M που οι πλευρές τους έχουν μήκος και ρόμβοι τύπου D που οι πλευρές n 2k τους έχουν μήκος. Αν m είναι το πλήθος των ρόμβων τύπου M και d το πλήθος των n ρόμβων τύπου D , να βρεθεί η σχέση που εκφράζει τη διαφορά m − d συναρτήσει του n ( n ακέραιος μεγαλύτερος του 1 ). Λύση k Κάθε ευθύγραμμο τμήμα μήκους (που δεν ανήκει στις πλευρές του n τριγώνου) είναι η διαγώνιος ενός και μόνο ρόμβου τύπου M. Για να υπολογίσουμε λοιπόν το πλήθος των ρόμβων τύπου M , αρκεί να υπολογίζουμε το πλήθος όλων των ευθυγράμμων τμημάτων που δημιουργούνται στο εσωτερικό του τριγώνου από την τομή των ευθυγράμμων τμημάτων που ενώνουν τα σημεία των πλευρών. Τα τμήματα που είναι παράλληλα με τη πλευρά BC είναι: n( n − 1 ) 1+ 2 + 3 + + (n −1)=. 2 Άρα το συνολικό πλήθος των ρόμβων τύπου M είναι: n( n − 1 ) m=3. 2 Για την μέτρηση των ρόμβων τύπου D θα χωρίσουμε τα εσωτερικά σημεία του τριγώνου σε τρείς κατηγορίες. Η πρώτη κατηγορία αποτελείται από εκείνα τα σημεία που είναι κέντρα ενός και μόνο ρόμβου τύπου D. Αυτά είναι πάντοτε τρία (δηλαδή είναι τρία για κάθε n ). Στο διπλανό σχήμα φαίνονται τα σημεία αυτά για n = 8. - 22 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Η δεύτερη κατηγορία αποτελείται από εκείνα τα σημεία που είναι κέντρα δύο και μόνο ρόμβων τύπου D. Τα σημεία αυτά βρίσκονται στα ευθύγραμμα τμήματα που είναι παράλληλα και πλησιέστερα προς τις πλευρές. Σε κάθε ευθύγραμμο τμήμα υπάρχουν n − 4 σημεία. Άρα συνολικά θα έχουμε 3( n − 4 ) σημεία αυτής της κατηγορίας. Στο διπλανό σχήμα φαίνονται τα σημεία αυτά για n = 8. Η Τρίτη κατηγορία τέλος αποτελείται από τα υπόλοιπα σημεία που είναι κέντρα τριών ρόμβων τύπου D. Αυτά τα σημεία είναι ( n − 5 )( n − 4 ) 1+ 2 + 3 + +( n − 5) =. 2 Στο διπλανό σχήμα φαίνονται τα σημεία αυτά για n = 8. Με τη βοήθεια των προηγούμενων παρατηρήσεων, καταλήγουμε στον υπολογισμό όλων των ρόμβων τύπου D , που είναι: ( n − 5 )( n − 4 ) 3 d = 3 + 3( n − 4 )2 + 3 = (2 + ( n − 1 )( n − 4 )). 2 2 (Προφανώς για n = 2 και n = 3 , ισχύει d = 0 ). Εκτελώντας πράξεις, καταλήγουμε m − d = 3( 2 n − 3 ). 2. 6 Π Ρ Ό Β ΛΗ Μ Α Ø Στο επίπεδο δίνονται n διαφορετικές μεταξύ τους ευθείες. Να βρεθεί το μέγιστο πλήθος των χωρίων στα οποία χωρίζουν το επίπεδο οι ευθείες αυτές. Λύση Έστω P (n) το μέγιστο πλήθος των χωρίων που δημιουργούν οι n ευθείες. Τότε προφανώς P(1) = 2 (διότι μία ευθεία χωρίζει σε δύο χωρία το επίπεδο). Σχήμα 1 Έστω τώρα και μία δεύτερη ευθεία στο επίπεδο. Τότε υπάρχουν οι εξής περιπτώσεις: 1 η περίπτωση Αν η δεύτερη ευθεία είναι παράλληλη προς την πρώτη τότε ορίζονται τρία χωρία. Δηλαδή δημιουργείται ένα επί πλέον χωρίο από το “προηγούμενο βήμα” ( P (1) + 1 = 2 + 1 = 3 χωρία). (Σχήμα 2 (α)) - 23 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Σχήμα 2 2 η περίπτωση Αν η δεύτερη ευθεία τέμνει την πρώτη τότε ορίζονται τέσσερα χωρία. Δηλαδή δημιουργούνται δύο επί πλέον χωρία από το “προηγούμενο βήμα” ( P (1) + 2 = 2 + 2 = 4 ). (Σχήμα 2 (β)) Έστω ακόμη μία τρίτη ευθεία στο επίπεδο. Τότε υπάρχουν οι εξής περιπτώσεις: 1 η περίπτωση Αν η τρίτη ευθεία είναι παράλληλη προς τις άλλες δύο (προσέξτε το σχήμα 3(α) σαν συνέχεια του σχήματος 2(α)) τότε ορίζονται τέσσερα χωρία. Δηλαδή δημιουργείται ένα επί πλέον χωρίο από το “προηγούμενο βήμα” ( P (2) + 1 ). (Σχήμα 3 (α)) 2 η περίπτωση Αν η τρίτη ευθεία τέμνει τις άλλες δύο (προσέξτε το σχήμα 3(β) σαν συνέχεια του σχήματος 2(α)) τότε ορίζονται έξι χωρία. Δηλαδή δημιουργούνται τρία επί πλέον χωρία από το “προηγούμενο βήμα” ( P (2 ) + 3 ). (Σχήμα 3 (β)) Σχήμα 3 3 η περίπτωση Αν η τρίτη ευθεία τέμνει τις άλλες δύο (προσέξτε το σχήμα 3(γ) σαν συνέχεια του σχήματος 2(β)) τότε ορίζονται επτά χωρία. Δηλαδή δημιουργούνται τέσσερα επί πλέον χωρία από το “προηγούμενο βήμα” ( P( 2 ) + 4 ). (Σχήμα 3 (γ)) - 24 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Σε όλες τις περιπτώσεις παρατηρούμε ότι με την “είσοδο” μίας νέας ευθείας, δημιουργούνται k + 1 καινούργια χωριά, όπου k είναι το πλήθος των σημείων τομής της “νεοεισερχόμενης” ευθείας με τις ήδη υπάρχουσες. Η προηγούμενη παρατήρηση , μαζί με το δεδομένο ότι “η ( n + 1 ) -οστή ευθεία μπορεί να τέμνει τις n προϋπάρχουσες ευθείες σε n το πολύ σημεία”, μας οδηγεί στη δημιουργία του παρακάτω αναγωγικού τύπου για το μέγιστο πλήθος P(n ) των χωρίων που δημιουργούν οι n διαφορετικές μεταξύ τους ευθείες: P( n + 1 ) ≤ P( n ) + n + 1. Από τη προηγούμενη ανισότητα, έχουμε: P( 1 ) = 2 ⎫ P( 2 ) ≤ P( 1 ) + 2 ⎪ ⎪ P( 3 ) ≤ P( 2 ) + 3 ⎪⎪ ⎬ ⎪ P( n − 1 ) ≤ P( n − 2 ) + n − 1⎪ ⎪ P( n ) ≤ P( n − 1 ) + n ⎪⎭ Προσθέτοντας τις σχέσεις κατά μέλη, καταλήγουμε: n2 + n + 2 P( n ) ≤. 2 Προφανώς η ισότητα ισχύει όταν οι ευθείες τέμνονται ανά δύο και ανά τρείς δεν περνάνε από το ίδιο σημείο. 2. 7 Π Ρ Ο Β ΛΗ ΜΑ Ø Στο επίπεδο δίνονται n διαφορετικές μεταξύ τους ευθείες που τέμνονται ανά δύο και ανά τρεις δεν περνάνε από το ίδιο σημείο. Να βρεθεί το πλήθος των φραγμένων και μη φραγμένων χωρίων που δημιουργούνται. Λύση Οποιαδήποτε δύο γειτονικά και μη φραγμένα χωρία χωρίζονται από ημιευθείες (Σχήματα 4(α) και 5(α)). Δηλαδή έχουν κοινό σύνορο ημιευθεία. Σχήμα 4 Αν τώρα θεωρήσουμε μία οποιαδήποτε ευθεία (τέμνουσα), τότε κάθε μία από τις δύο ημιευθείες που αποτελούν μέρη της, χωρίζουν δύο ακριβώς μη φραγμένα χωρία άρα τα μη φραγμένα χωρία είναι 2 n. - 25 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Σχήμα 5 n2 + n + 2 Αν τώρα χρησιμοποιήσουμε τη σχέση P( n ) = που μας δίνει το πλήθος όλων των 2 n 2 − 3n + 2 χωρίων, καταλήγουμε ότι το πλήθος των φραγμένων χωρίων είναι:. 2 2.8 Π ΡΟ Β ΛΗ ΜΑ Στο επίπεδο θεωρούμε k + n διαφορετικές μεταξύ τους ευθείες οι οποίες ανά τρεις δεν περνάνε από το ίδιο σημείο (όπου k ακέραιος με k > 1 και n θετικός ακέραιος). Από τις ευθείες αυτές , k είναι παράλληλες μεταξύ τους ενώ οι υπόλοιπες n δεν είναι παράλληλες μεταξύ τους (τέμνονται ανά δύο). Επίσης δεν υπάρχει κάποια ευθεία (από τις n ) που να είναι παράλληλη με τις k παράλληλες ευθείες. Όλες οι παραπάνω ευθείες τεμνόμενες χωρίζουν το επίπεδο σε χωρία (πχ τριγωνικά, πολυγωνικά και μη φραγμένα). Ένα χωρίο θα το ονομάζουμε “καλό” όταν βρίσκεται ανάμεσα στις παράλληλες ευθείες. Αν σε ένα σχηματισμό, το ελάχιστο πλήθος των “καλών” χωρίων είναι 176 και το μέγιστο 221, να βρεθούν τα k , n. Προφανώς οι k (διαφορετικές μεταξύ τους) παράλληλες ευθείες ορίζουν k − 1 διαδοχικές παράλληλες “λωρίδες” στο επίπεδο. Επίσης οι n διαφορετικές, μη παράλληλες μεταξύ τους ευθείες, τέμνονται ανά δύο σε ⎛ n ⎞ n(n − 1) ⎜⎜ ⎟⎟ = σημεία. ⎝2⎠ 2 Διακρίνουμε τώρα δύο περιπτώσεις. ⎛ n⎞ 1 η Περίπτωση: Τα ⎜⎜ ⎟⎟ σημεία τομής των n ευθειών (που τέμνονται ανά δύο), βρίσκονται εκτός ⎝ 2⎠ των παράλληλων “λωρίδων”. - 26 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Σχήμα 6 Στη περίπτωση αυτή κάθε μία από τις n ευθείες ορίζει σε κάθε “λωρίδα” n + 1 “καλά” χωρία. Οπότε ορίζονται συνολικά (k − 1)(n + 1) συνολικά “καλά” χωρία. Στο (Σχήμα 1) βλέπουμε τα “καλά” χωρία που δημιουργούνται από n = 3 ευθείες. ⎛n⎞ Αν τώρα ένα από τα ⎜⎜ ⎟⎟ σημεία τομής των n ευθειών το θεωρήσουμε μέσα σε μία λωρίδα, τότε ⎝2⎠ στη λωρίδα αυτή θα δημιουργηθεί ένα επί πλέον “καλό” χωρίο (Σχήμα 2). Σχήμα 7 - 27 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Άρα ( k − 1 )( n + 1 ) είναι ο ελάχιστος αριθμός “καλών” χωρίων που μπορούν να δημιουργηθούν, ⎛n⎞ διότι με την είσοδο καθενός από τα ⎜⎜ ⎟⎟ σημεία τομής στις λωρίδες, αυξάνεται ο αριθμός των ⎝2⎠ “καλών” χωρίων. ⎛ n⎞ 2 η Περίπτωση: Τα ⎜⎜ ⎟⎟ σημεία τομής των n ευθειών (που τέμνονται ανά δύο), βρίσκονται εντός ⎝ 2⎠ των παράλληλων λωρίδων. Συνεχίζοντας τη διαδικασία εισαγωγής των σημείων τομής μέσα στις “λωρίδες”, θα προστίθεται ⎛n⎞ κάθε φορά και ένα “καλό” χωρίο. Έτσι στο τέλος θα έχουμε επί πλέον ⎜⎜ ⎟⎟ “καλά” χωρία. ⎝2⎠ Σχήμα 8 Τελικά ο μέγιστος αριθμός των “καλών” χωρίων είναι: n( n − 1 ) ( k − 1 )( n + 1 ) +. 2 Εφόσον τώρα (σύμφωνα με τα δεδομένα του προβλήματος), ο ελάχιστος αριθμός των “καλών” χωρίων είναι 176 και ο μέγιστος 221 , θα ισχύει: ⎧⎪ ( k − 1 )( n + 1 ) = 176 ⎧⎪ ( k − 1 )( n + 1 ) = 176 ⎨( k − 1 )( n + 1 ) + n( n − 1 ) = 221 ⇔ ⎨176 + n( n − 1 ) = 221 ⇔ ⎪⎩ 2 ⎪⎩ 2 ⎧⎪ ( k − 1 )( n + 1 ) = 176 ⇔⎨ n( n − 1 ). ⎪⎩176 + 2 = 221 Λύνουμε το σύστημα και βρίσκουμε k = 17, n = 10. - 28 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ 2 ος Τρόπος υπολογισμού του μέγιστου αριθμού των καλών χωρίων. Με τη συλλογιστική που αναπτύχθηκε στον προηγούμενο τρόπο, ο μέγιστος αριθμός των καλών χωρίων επιτυγχάνεται όταν τα σημεία τομής των τεμνομένων ευθειών βρεθούν μέσα στις λωρίδες που δημιουργούν οι παράλληλες ευθείες. Θα υπολογίσουμε λοιπόν όλα τα χωρία που δημιουργούνται από τις k + n διαφορετικές μεταξύ τους ευθείες και στη συνέχεια θα αφαιρέσουμε τα χωρία που βρίσκονται εκτός των παραλλήλων (έχοντας πάντα υπ΄ όψιν ότι τα σημεία τομής των τεμνομένων ευθειών βρίσκονται μέσα στις λωρίδες που δημιουργούν οι παράλληλες ευθείες). Έστω p(m) το πλήθος των χωρίων στα οποία χωρίζεται το επίπεδο από m ευθείες οι οποίες δεν διέρχονται ανά τρεις από το ίδιο σημείο. Προφανώς p (1) = 2. Θεωρούμε τώρα ότι p (m) είναι το πλήθος των χωρίων στα οποία χωρίζεται το επίπεδο από τις m ευθείες και φέρουμε μία επί πλέον ευθεία με σκοπό να υπολογίσουμε επαγωγικά το p (m + 1). Προφανώς p (m + 1) = p (m) + r. Όπου r είναι το πλήθος των επί πλέον χωρίων που ης “δημιουργούνται” με τη χάραξη της m + 1 ευθείας. Με τη χάραξη λοιπόν της m + 1 ης ευθείας “δημιουργούνται” τόσα επί πλέον χωρία, όσα είναι τα σημεία τομής της με τις υπόλοιπες ευθείες αυξημένα κατά ένα. Αν δηλαδή η m + 1 ευθεία είναι παράλληλη με κάποια από τις προηγούμενες ευθείες, τότε τα σημεία τομής της θα είναι m − 1 και κατά συνέπεια “δημιουργούνται” r = m επί πλέον χωρία. Αν όμως η m + 1 ευθεία δεν είναι παράλληλη με κάποια από τις προηγούμενες ευθείες, τότε τα σημεία τομής της θα είναι m και κατά συνέπεια “δημιουργούνται” r = m + 1 επί πλέον χωρία. Αν λοιπόν οι ευθείες δεν είναι ανά δύο παράλληλες μεταξύ τους και δεν διέρχονται ανά τρεις από το ίδιο σημείο, μπορούμε να διατυπώσουμε την αναδρομική σχέση: p (m) = p (m − 1) + m και m2 + m + 2 p (1) = 2. Από τη σχέση αυτή προκύπτει: p (m) =. 2 - 29 - ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ Θεωρώντας τώρα τα δεδομένα του προβλήματος, συμπεραίνουμε ότι τα χωρία που n2 + n + 2 “δημιουργούνται” , είναι: + k (n +1). 2 Τα καλά χωρία προκύπτουν αν αφαιρέσουμε τα 2( n + 1) που βρίσκονται εκτός των παραλλήλων ευθειών. 2.9 Π Ρ Ο Β ΛΗ ΜΑ Ø Στο εσωτερικό κάθε μίας από τις πλευρές τετραγώνου θεωρούμε n διαφορετικά μεταξύ τους σημεία. Να βρεθεί ο πλήθος όλων των τριγώνων που έχουν κορυφές τα σημεία αυτά. Λύση (1 ος τρόπος) Από τα 4 n σημεία που βρίσκονται στις πλευρές του τετραγώνου μπορούμε να δημιουργήσουμε ⎛ 4n ⎞ ⎜⎜ ⎟⎟ τριάδες σημείων. Όλες βέβαια αυτές οι τριάδες σημείων, δεν ορίζουν τρίγωνα γιατί κάποιες ⎝ 3⎠ ⎛n ⎞ τριάδες αποτελούνται από συνευθειακά σημεία. Σε κάθε πλευρά υπάρχουν ⎜⎜ ⎟⎟ το πλήθος τριάδες ⎝3 ⎠ που αποτελούνται από συνευθειακά σημεία. Άρα δημιουργούνται: ⎛ 4n ⎞ ⎛ n ⎞ ⎜⎜ ⎟⎟ − 4⎜⎜ ⎟⎟ = 2n 2 (5n − 3) τρίγωνα. ⎝ 3 ⎠ ⎝3⎠ ος Λύση (2 τρόπος) Τα τρίγωνα που δημιουργούνται, μπορούμε να τα χωρίσουμε σε δύο τύπους. Σαν τρίγωνα πρώτου τύπου θεωρούμε αυτά των οποίων και οι τρείς κορυφές ανήκουν σε διαφορετικές πλευρές του τετραγώνου ενώ σαν τρίγωνα δεύτερου τύπου θεωρούμε αυτά που οι δύο κορυφές ανήκουν στην ίδια πλευρά του τετραγώνου και η τρίτη κορυφή σε διαφορετική πλευρά. Το πλήθος των τριγώνων πρώτου τύπου είναι 4n3 (*) και το πλήθος των τριγώνων δευτέρου τύπου ⎛n⎞ ⎛n⎞ είναι 3 ⋅ 4n⎜⎜ ⎟⎟ (**), άρα το πλήθος των τριγώνων είναι 4n3 + 3 ⋅ 4n⎜⎜ ⎟⎟ = 2n 2 (5n − 3). ⎝ 2⎠ ⎝2⎠ (*) Τις τρείς από τις τέσσερεις πλευρές του τετραγώνου (επάνω στις οποίες θα βρίσκονται οι ⎛ 4⎞ κορυφές των τριγώνων) μπορούμε να τις επιλέξουμε με ⎜⎜ ⎟⎟ = 4 τρόπους. Ταυτόχρονα μπορούμε να ⎝ 3⎠ επιλέξουμε κάθε κορυφή με n διαφορετικούς τρόπους. Άρα η εκλογή τριγώνων πρώτου τύπου μπορεί να γίνει (σύμφωνα με τη πολλαπλασιαστική αρχή) με 4n3 διαφορετικούς τρόπους. (**) Τις δύο από τις τέσσερεις πλευρές του τετραγώνου (επάνω στις οποίες θα βρίσκονται οι ⎛4⎞ κορυφές των τριγώνων) μπορούμε να τις επιλέξουμε με ⎜⎜ ⎟⎟ = 3⋅ 4 τρόπους. Ταυτόχρονα μπορούμε ⎝2⎠ να επιλέξουμε τη μία κορυφή με n διαφορετικούς τρόπους και τις δύο άλλες κορυφές (που θα ⎛n⎞ ανήκουν στην ίδια πλευρά με ⎜⎜ ⎟⎟ διαφορετικούς τρόπους. Άρα (σύμφωνα με τη ⎝2⎠ - 30 -  ΣΥΝΔΥΑΣΤΙΚΗ ΓΙΑ ΟΛΥΜΠΙΑΔΕΣ ⎛ n⎞ πολλαπλασιαστική αρχή) η εκλογή τριγώνων δευτέρου τύπου μπορεί να γίνει με 3 ⋅ 4 n⎜⎜ ⎟⎟ ⎝ 2⎠ διαφορετικούς τρόπους. 2. 1 0 Π Ρ ΟΒ Λ Η ΜΑ Ø Δίνεται στο επίπεδο ένα σύνολο S από n το πλήθος ( n ≥ 3 ) διαφορετικά μεταξύ τους n( n − 2 ) σημεία που ανά τρία δεν ανήκουν στην ίδια ευθεία. Αποδείξτε ότι υπάρχουν 3 τουλάχιστον τρίγωνα με κορυφές σημεία του συνόλου S , που δεν περιέχουν άλλο στοιχείο του συνόλου S. Λύση Ένα τρίγωνο που δεν περιέχει άλλα στοιχείο του σημειοσυνόλου S θα το ονομάζουμε “κενό”. Προσπαθούμε λοιπόν να υπολογίσουμε το ελάχιστο πλήθος των “κενών” τριγώνων που μπορούν να δημιουργηθούν. Είναι γνωστό ότι η ευθεία που ορίζουν δύο οποιαδήποτε διαφορετικ