Double Counting
Η Διπλή Καταμέτρηση είναι μια πανέξυπνη τεχνική: μετράς την ίδια ποσότητα με δύο διαφορετικούς τρόπους, και μετά εξισώνεις τα αποτελέσματα! Αυτό σου δίνει μια σχέση που συχνά είναι πολύ χρήσιμη.
Κλασικό παράδειγμα: Σε ένα πάρτι, κάθε άτομο χειραψιάστηκε με κάποια άλλα άτομα. Το σύνολο των χειραψιών μπορεί να μετρηθεί:
Και τα δύο μετρούν το ίδιο πράγμα!
🔑 Πότε να τη διαλέξεις:
Σε ένα πάρτι με \(n\) άτομα, κάθε άτομο χειράψιαστηκε με κάποια άλλα. Έστω \(d_i\) ο αριθμός χειραψιών του \(i\)-οστού ατόμου.
Αποδείξτε ότι το άθροισμα \(d_1 + d_2 + \cdots + d_n\) είναι άρτιος αριθμός.
Hint: Μέτρησε τις χειραψίες με δύο τρόπους!
Τρόπος 1: Από τα άτομα - κάθε άτομο συνεισφέρει \(d_i\) χειραψίες
Τρόπος 2: Από τις χειραψίες - κάθε χειραψία μετράει 2 φορές (μία για κάθε άτομο)!
Κλειδί: Άθροισμα = 2 × (πλήθος χειραψιών)
Βήμα 1 - Εντοπισμός ποσότητας:
Θα μετρήσουμε το συνολικό πλήθος χειραψιών.
Βήμα 2 - Τρόπος 1 (από τα άτομα):
Κάθε άτομο \(i\) έκανε \(d_i\) χειραψίες.
Άθροισμα: \(d_1 + d_2 + \cdots + d_n\)
Βήμα 3 - Τρόπος 2 (από τις χειραψίες):
Κάθε χειραψία αφορά ακριβώς 2 άτομα.
Άρα κάθε χειραψία μετράται 2 φορές στο άθροισμα (μία για κάθε άτομο)!
Αν υπάρχουν \(H\) χειραψίες συνολικά, τότε το άθροισμα = \(2H\).
Βήμα 4 - Εξίσωση:
\[d_1 + d_2 + \cdots + d_n = 2H\]
Συμπέρασμα: Το άθροισμα είναι άρτιος αριθμός (γιατί είναι \(2H\))! ✓
🔑 Κλειδί: Μετρήσαμε το ίδιο πράγμα με δύο τρόπους και εξισώσαμε!
Σε ένα τουρνουά, \(n\) ομάδες παίζουν μεταξύ τους. Κάθε παιχνίδι έχει νικητή (δεν υπάρχουν ισοπαλίες). Έστω \(w_i\) ο αριθμός νικών της \(i\)-οστής ομάδας και \(l_i\) ο αριθμός ηττών της.
Αποδείξτε ότι: \(w_1^2 + w_2^2 + \cdots + w_n^2 = l_1^2 + l_2^2 + \cdots + l_n^2\)
Hint: Μέτρησε το πλήθος ζευγαριών παιχνιδιών που η ομάδα \(i\) νίκησε την ομάδα \(j\)!
Τρόπος 1: Για κάθε νικήτρια ομάδα, μέτρα τα ζεύγη (παιχνίδι, ηττημένος)
Τρόπος 2: Για κάθε ηττημένη ομάδα, μέτρα τα ζεύγη (παιχνίδι, νικητής)
Κλειδί: Και οι δύο τρόποι μετρούν το ίδιο πλήθος ζευγαριών!
Παρατήρηση: Σε ένα τουρνουά όπου όλοι παίζουν με όλους, κάθε ομάδα παίζει ακριβώς \(n-1\) παιχνίδια.
Άρα: \(w_i + l_i = n - 1\) για κάθε \(i\).
Βήμα 1 - Εντοπισμός ποσότητας:
Θα μετρήσουμε τα ταξινομημένα ζεύγη παιχνιδιών (P, Q) όπου η ομάδα \(P\) νίκησε τόσο την ομάδα \(Q\) όσο και κάποια τρίτη ομάδα.
Βήμα 2 - Τρόπος 1 (από τις νίκες):
Για κάθε ομάδα \(i\) με \(w_i\) νίκες:
Μπορούμε να διαλέξουμε 2 από τις \(w_i\) ομάδες που νίκησε με \(\binom{w_i}{2} = \frac{w_i(w_i-1)}{2}\) τρόπους.
Συνολικά: \(\sum_{i=1}^{n} \binom{w_i}{2} = \sum_{i=1}^{n} \frac{w_i(w_i-1)}{2}\)
Βήμα 3 - Τρόπος 2 (από τις ήττες):
Για κάθε ομάδα \(j\) με \(l_j\) ήττες:
Μπορούμε να διαλέξουμε 2 από τις \(l_j\) ομάδες που τη νίκησαν με \(\binom{l_j}{2}\) τρόπους.
Συνολικά: \(\sum_{j=1}^{n} \binom{l_j}{2} = \sum_{j=1}^{n} \frac{l_j(l_j-1)}{2}\)
Βήμα 4 - Εξίσωση:
Και οι δύο τρόποι μετρούν το ίδιο πράγμα!
\[\sum_{i=1}^{n} \frac{w_i(w_i-1)}{2} = \sum_{j=1}^{n} \frac{l_j(l_j-1)}{2}\]
\[\sum w_i^2 - \sum w_i = \sum l_j^2 - \sum l_j\]
Βήμα 5 - Χρήση ότι \(\sum w_i = \sum l_j\):
Κάθε παιχνίδι έχει ακριβώς έναν νικητή και έναν ηττημένο, άρα συνολικές νίκες = συνολικές ήττες.
Επομένως: \[\sum w_i^2 = \sum l_j^2\] ✓
🔑 Κλειδί: Μετρήσαμε ζεύγη (νικήτρια, δύο ηττημένες) με δύο τρόπους!
Δίνεται γράφος με \(n\) κορυφές. Έστω \(d_i\) ο βαθμός της κορυφής \(i\) και \(e\) το πλήθος των ακμών.
Αποδείξτε ότι: \(\sum_{i=1}^{n} d_i = 2e\)
Επίσης, αποδείξτε ότι το πλήθος των κορυφών με περιττό βαθμό είναι άρτιο.
Hint: Μέτρησε τα "άκρα" των ακμών!
Τρόπος 1: Από τις κορυφές - κάθε κορυφή έχει \(d_i\) άκρα
Τρόπος 2: Από τις ακμές - κάθε ακμή έχει ακριβώς 2 άκρα
Κλειδί: Για το δεύτερο ερώτημα, χρησιμοποίησε ισοτιμία mod 2!
Μέρος 1: \(\sum d_i = 2e\)
Βήμα 1 - Εντοπισμός ποσότητας:
Θα μετρήσουμε το πλήθος των "άκρων" των ακμών (incidences).
Βήμα 2 - Τρόπος 1 (από τις κορυφές):
Κάθε κορυφή \(i\) με βαθμό \(d_i\) συνεισφέρει \(d_i\) άκρα.
Συνολικά: \(\sum_{i=1}^{n} d_i\)
Βήμα 3 - Τρόπος 2 (από τις ακμές):
Κάθε ακμή συνδέει ακριβώς 2 κορυφές, άρα έχει 2 άκρα.
Συνολικά: \(2e\)
Βήμα 4 - Εξίσωση:
\[\sum_{i=1}^{n} d_i = 2e\] ✓
Μέρος 2: Πλήθος κορυφών με περιττό βαθμό είναι άρτιο
Απόδειξη:
Έστω \(O\) = πλήθος κορυφών με περιττό βαθμό, \(E\) = πλήθος κορυφών με άρτιο βαθμό.
Από το Μέρος 1: \(\sum d_i = 2e\) (άρτιο)
Χωρίζουμε το άθροισμα:
\[\sum_{\text{άρτιο } d_i} d_i + \sum_{\text{περιττό } d_i} d_i = 2e\]
Το πρώτο άθροισμα είναι άρτιο (άθροισμα άρτιων).
Άρα το δεύτερο άθροισμα πρέπει να είναι άρτιο!
Αλλά το δεύτερο άθροισμα είναι άθροισμα \(O\) περιττών αριθμών.
Άθροισμα περιττών αριθμών είναι άρτιο ⟺ το πλήθος τους είναι άρτιο!
Άρα \(O\) είναι άρτιος! ✓
🔑 Κλειδί: Η διπλή καταμέτρηση συν ισοτιμία mod 2 έδωσε το αποτέλεσμα!
Ερώτηση: Γιατί λέγεται "Διπλή" καταμέτρηση;