Συνδυαστική και πιθανότητες
Περιστερώνας, αναλλοίωτα και μονοτονικά μεγέθη, γεννήτριες συναρτήσεις με φίλτρο ριζών της μονάδας, και γραμμικότητα της μέσης τιμής με δείκτριες.
Αρχή του περιστερώνα
Αν αντικείμενα μπουν σε κουτιά, κάποιο κουτί έχει δύο. Η δυσκολία είναι πάντα να διαλέξεις τα κουτιά.
- Μερικά αθροίσματα modulo . Ανάμεσα σε οποιουσδήποτε ακέραιους υπάρχει μη κενό σύνολο διαδοχικών με άθροισμα πολλαπλάσιο του . Κουτιά: τα υπόλοιπα των (με ), που είναι αριθμοί για υπόλοιπα.
- Από τα , κάθε αριθμοί περιέχουν δύο διαδοχικούς (κουτιά ), άρα δύο πρώτους μεταξύ τους.
Αναλλοίωτα και μονοτονικά μεγέθη
Μια διαδικασία αλλάζει μια κατάσταση με κάποιες επιτρεπτές κινήσεις. Για να δείξεις ότι μια κατάσταση δεν φτάνεται, βρες ποσότητα που δεν αλλάζει με καμία κίνηση: άρτιο/περιττό, άθροισμα modulo , χρωματισμό, ορίζουσα. Για να δείξεις ότι η διαδικασία τελειώνει, βρες μη αρνητικό ακέραιο που μειώνεται γνησίως σε κάθε κίνηση.
Γεννήτριες συναρτήσεις
Η ακολουθία γίνεται η σειρά . Ένα πρόβλημα μέτρησης γίνεται άλγεβρα πολυωνύμων.
- Διαμερίσεις. Οι διαμερίσεις του σε διαφορετικά μέρη έχουν γεννήτρια , και σε περιττά μέρη . Οι δύο είναι ίσες, επειδή , οπότε τα πλήθη είναι ίσα (Euler).
- Φίλτρο ριζών της μονάδας. Με , και επειδή είναι όταν και αλλιώς:
Γραμμικότητα της μέσης τιμής
πάντα, χωρίς ανεξαρτησία. Γράψε τη ζητούμενη ποσότητα ως άθροισμα δεικτριών , οπότε .
- Σταθερά σημεία τυχαίας μετάθεσης: , και κάθε όρος έχει πιθανότητα . Άρα για κάθε .
- Πιθανοτική μέθοδος: αν , υπάρχει αποτέλεσμα με και αποτέλεσμα με . Αν για ακέραια , τότε .
Παγίδες
- Η διασπορά δεν είναι γραμμική. μόνο για ασυσχέτιστες μεταβλητές.
- Ένωση: , με ισότητα μόνο για ξένα (σχεδόν βέβαια) ενδεχόμενα.
- Στις γεννήτριες δούλευε με τυπικές δυναμοσειρές, ή γράψε πού συγκλίνουν πριν βάλεις τιμή στο .
Για μελέτη
- Gelca & Andreescu, Putnam and Beyond, §1.3 (The Pigeonhole Principle)
- Gelca & Andreescu, Putnam and Beyond, §1.5 (Invariants and Semi-Invariants)
- Morris, Συνδυαστική (μτφρ. Σ. Νικολόπουλος, Κάλλιπος, CC BY-NC-SA 4.0), §7 (Γεννήτριες Συναρτήσεις)
- Morris, Συνδυαστική (μτφρ. Σ. Νικολόπουλος, Κάλλιπος, CC BY-NC-SA 4.0), §8 (Γεννήτριες Συναρτήσεις και Αναδρομή)
- Gelca & Andreescu, Putnam and Beyond, §6.2.2 (Generating Functions)
- Gelca & Andreescu, Putnam and Beyond, §6.3 (Probability)
Θέματα διαγωνισμών με αυτά τα εργαλεία
Δεν υπάρχουν ακόμα θέματα με αυτά τα εργαλεία.