Special & Boundary Cases
Η στρατηγική των Ειδικών & Οριακών Περιπτώσεων είναι απλή αλλά εξαιρετικά ισχυρή: πριν επιχειρήσεις τη γενική περίπτωση, δοκίμασε τα άκρα!
Τι είναι "ειδική περίπτωση"; Είναι όταν μία μεταβλητή παίρνει μία ακραία τιμή: \(n = 1\), \(x = 0\), \(k = n\), κλπ. Αυτές οι περιπτώσεις συχνά:
🔑 Πότε να τη διαλέξεις:
Παράδειγμα: "Αποδείξτε ότι \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\) για κάθε \(n \geq 1\)."
Ειδικές περιπτώσεις:
Τώρα έχεις confidence ότι ο τύπος είναι σωστός!
Ένας μαθητής ισχυρίζεται ότι για κάθε θετικό ακέραιο \(n\), ισχύει:
\[n^2 + n + 41 \text{ είναι πρώτος αριθμός}\]
Ελέγξτε αν η πρόταση είναι αληθής ή ψευδής.
Hint: Δοκίμασε μερικές ειδικές τιμές του \(n\)!
Ξεκίνα από \(n = 1, 2, 3, \ldots\) και δες αν βρεις κάποιο \(n\) για το οποίο ο τύπος δίνει σύνθετο αριθμό.
Κλειδί: Υπάρχει κάποιο \(n\) που κάνει τον τύπο "ύποπτο";
Βήμα 1 - Δοκιμή μικρών τιμών:
Μέχρι τώρα δουλεύει! Αλλά...
Βήμα 2 - Ύποπτη τιμή:
Τι συμβαίνει όταν \(n = 41\);
\[n^2 + n + 41 = 41^2 + 41 + 41 = 41(41 + 1 + 1) = 41 \cdot 43\]
Αυτός ο αριθμός είναι σύνθετος! (γινόμενο του 41 και 43) ✗
Συμπέρασμα: Η πρόταση είναι ψευδής!
🔑 Κλειδί: Η "οριακή" τιμή \(n = 41\) αποκάλυψε το λάθος!
Αποδείξτε ότι για κάθε θετικό ακέραιο \(n\), ο αριθμός:
\[n^3 - n\]
διαιρείται με το 6.
Hint: Δοκίμασε πρώτα \(n = 1, 2, 3\) για να πάρεις intuition!
Μετά σκέψου: πώς μπορείς να παραγοντοποιήσεις τον τύπο \(n^3 - n\);
Κλειδί: Αν παραγοντοποιήσεις, θα δεις ότι είναι γινόμενο τριών διαδοχικών αριθμών!
Βήμα 1 - Ειδικές περιπτώσεις (για intuition):
Φαίνεται να δουλεύει!
Βήμα 2 - Παραγοντοποίηση:
\[n^3 - n = n(n^2 - 1) = n(n-1)(n+1)\]
Δηλαδή είναι γινόμενο τριών διαδοχικών ακεραίων: \((n-1) \cdot n \cdot (n+1)\)
Βήμα 3 - Διαιρετότητα:
Άρα το γινόμενο διαιρείται με \(2 \times 3 = 6\). ✓
🔑 Κλειδί: Οι ειδικές περιπτώσεις μας έδειξαν το pattern, η παραγοντοποίηση το απέδειξε!
Σε έναν πίνακα \(n \times n\) γράφουμε τους αριθμούς \(1, 2, 3, \ldots, n^2\). Αποδείξτε ότι υπάρχουν δύο γειτονικά κελιά (με κοινή πλευρά) των οποίων οι αριθμοί διαφέρουν κατά τουλάχιστον \(n\).
Hint: Δοκίμασε πρώτα \(n = 2\) και \(n = 3\) για να δεις τι συμβαίνει!
Σκέψου: ποια είναι η μέγιστη διαφορά μεταξύ γειτονικών κελιών αν προσπαθήσεις να την ελαχιστοποιήσεις;
Κλειδί: Χρησιμοποίησε την Αρχή Περιστερώνα!
Βήμα 1 - Ειδική περίπτωση \(n = 2\):
Πίνακας \(2 \times 2\) με αριθμούς 1, 2, 3, 4.
Η μέγιστη διαφορά είναι \(4 - 1 = 3 \geq 2\). ✓
Βήμα 2 - Ειδική περίπτωση \(n = 3\):
Πίνακας \(3 \times 3\) με αριθμούς 1, 2, ..., 9.
Όποια διάταξη και να διαλέξουμε, θα υπάρχουν γειτονικά με διαφορά \(\geq 3\). ✓
Βήμα 3 - Γενική απόδειξη:
Θεωρούμε το μονοπάτι που ξεκινάει από το κελί με το 1 και καταλήγει στο κελί με το \(n^2\).
Αυτό το μονοπάτι έχει μήκος τουλάχιστον \(n-1\) βήματα (γιατί πρέπει να διασχίσουμε τουλάχιστον \(n-1\) σειρές ή στήλες).
Η συνολική διαφορά είναι: \(n^2 - 1\)
Αν κάθε βήμα αύξανε τον αριθμό κατά το πολύ \(n-1\), τότε:
Συνολική αύξηση \(\leq (n-1) \times (n-1) = n^2 - 2n + 1 < n^2 - 1\) ✗
Άρα κάποιο βήμα πρέπει να έχει διαφορά \(\geq n\). ✓
🔑 Κλειδί: Οι ειδικές περιπτώσεις μας έδωσαν intuition, η Αρχή Περιστερώνα την απόδειξη!
Ερώτηση: Γιατί δοκιμάζουμε ειδικές περιπτώσεις;