29-04-08
00:19
Στα παρακάτω θα συμβολίζουμε με C(N,K) τους συνδυασμούς των Ν ανά Κ.
Δηλαδή C(N,K) = Ν!/(Κ!(Ν-Κ)!)
Θα βρούμε ένα κάτω φράγμα για το Δ(Ν,Κ).
Ας πάρουμε πρώτα ένα παράδειγμα, για Ν=7 και Κ=3. Δηλαδή η κλήρωση βγάζει 3 αριθμούς από το σύνολο {1,2,3,4,5,6,7}
Οι πιθανές τριάδες είναι:
1 2 3
1 2 4
1 2 5
1 2 6
.....
4 5 7
5 6 7
το πλήθος C(7,3)=35
Ας υποθέσουμε ότι στην τριάδα που έχω παίξει περιλαμβάνεται το ζεύγος 1-2. Θα έχω κέρδος στην περίπτωση που η τριάδα που θα κληρωθεί θα είναι μία από τις 123,124,125,126,127.
Δηλαδή με ένα ζευγάρι καλύπτω 5 διαφορετικές τριάδες.
Επειδή υπάρχουν συνολικά 35 τριάδες, στην καλύτερη περίπτωση θα χρειαστώ 35:5=7 διαφορετικά ζεύγη
Όμως, κάθε τριάδα από αυτές που έχω παίξει περιέχει τρία ζεύγη. Επομένως, στην καλύτερη περίπτωση θα χρειαστώ μόνο 7:3=2.33 τριάδες
Δηλαδή Δ(7,3)>=2.33 που σημαίνει αναγκαστικά Δ(7,3)>=3 (όντως είναι ίσο με 4)
Στη γενική μορφή που έχουμε Ν ανά Κ οι παραπάνω σχέσεις γράφονται:
που μπορεί να μην είναι καλή προσέγγιση, είναι όμως ένα κάτω φράγμα, αρκετό για να μας απογοητεύσει αφού στην περίπτωση του ΛΟΤΤΟ θα πάρουμε Δ(49,6) >= C(49,5)/6^2 = 52969
Δηλαδή για να εξασφαλίσουμε βέβαιο 5άρι πρέπει να παίξουμε σίγουρα περισσότερες από 52969 στήλες, που είναι κάτι ασύμφορο αν υπολογίσουμε ότι θα μας κοστίσουν περισσότερο από 7945 ευρώ ενώ το 5άρι συνήθως δίνει γύρω στα 1000 ευρώ μέσο όρο με μέγιστο 2300 ευρώ για όλο το 2007
Παρατήρηση
Το 52969 είναι μόνο ένα κάτω φράγμα, η αληθινή τιμή μπορεί να είναι πολύ μεγαλύτερη
Δηλαδή C(N,K) = Ν!/(Κ!(Ν-Κ)!)
Θα βρούμε ένα κάτω φράγμα για το Δ(Ν,Κ).
Ας πάρουμε πρώτα ένα παράδειγμα, για Ν=7 και Κ=3. Δηλαδή η κλήρωση βγάζει 3 αριθμούς από το σύνολο {1,2,3,4,5,6,7}
Οι πιθανές τριάδες είναι:
1 2 3
1 2 4
1 2 5
1 2 6
.....
4 5 7
5 6 7
το πλήθος C(7,3)=35
Ας υποθέσουμε ότι στην τριάδα που έχω παίξει περιλαμβάνεται το ζεύγος 1-2. Θα έχω κέρδος στην περίπτωση που η τριάδα που θα κληρωθεί θα είναι μία από τις 123,124,125,126,127.
Δηλαδή με ένα ζευγάρι καλύπτω 5 διαφορετικές τριάδες.
Επειδή υπάρχουν συνολικά 35 τριάδες, στην καλύτερη περίπτωση θα χρειαστώ 35:5=7 διαφορετικά ζεύγη
Όμως, κάθε τριάδα από αυτές που έχω παίξει περιέχει τρία ζεύγη. Επομένως, στην καλύτερη περίπτωση θα χρειαστώ μόνο 7:3=2.33 τριάδες
Δηλαδή Δ(7,3)>=2.33 που σημαίνει αναγκαστικά Δ(7,3)>=3 (όντως είναι ίσο με 4)
Στη γενική μορφή που έχουμε Ν ανά Κ οι παραπάνω σχέσεις γράφονται:
- Συνολικά C(N,K) δυνατές Κ-άδες
- Με κάθε (Κ-1)άδα καλύπτω Ν-Κ+1 Κ-άδες
- Στην καλύτερη περίπτωση θα χρειαστώ C(N,K)/(N-K+1) το πλήθος (Κ-1)άδες
- Και αυτό πρέπει να το διαιρέσουμε με το Κ, γιατί τόσες είναι οι (Κ-1)άδες που περιέχονται σε μία Κ-άδα
που μπορεί να μην είναι καλή προσέγγιση, είναι όμως ένα κάτω φράγμα, αρκετό για να μας απογοητεύσει αφού στην περίπτωση του ΛΟΤΤΟ θα πάρουμε Δ(49,6) >= C(49,5)/6^2 = 52969
Δηλαδή για να εξασφαλίσουμε βέβαιο 5άρι πρέπει να παίξουμε σίγουρα περισσότερες από 52969 στήλες, που είναι κάτι ασύμφορο αν υπολογίσουμε ότι θα μας κοστίσουν περισσότερο από 7945 ευρώ ενώ το 5άρι συνήθως δίνει γύρω στα 1000 ευρώ μέσο όρο με μέγιστο 2300 ευρώ για όλο το 2007
Παρατήρηση
Το 52969 είναι μόνο ένα κάτω φράγμα, η αληθινή τιμή μπορεί να είναι πολύ μεγαλύτερη
Σημείωση: Το μήνυμα αυτό γράφτηκε 16 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.
25-04-08
23:31
Κοιτάζω την απάντηση σου φραππέ αλλα ομολογώ οτι δεν κατάλαβα το ελυσες; η και εσύ το ψάχνεις ακόμα;
Τα νούμερα που δίνω είναι όσα έχω βρει μέχρι στιγμής.
Δεν το έχω λύσει με μαθηματικά. Έχω γράψει ένα πρόγραμμα στον υπολογιστή που τα βρίσκει, αλλά είναι εξαιρετικά αργό.
Σημείωση: Το μήνυμα αυτό γράφτηκε 16 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.
25-04-08
23:02
Ωραίος προβληματισμός, Skeptikistis!
Έχουμε λοιπόν συνδυασμούς των Ν αντικειμένων ανά Κ και θέλουμε να μαντέψουμε τουλάχιστον Κ-1 από τα Κ επιλεγμένα αντικείμενα. Σκοπός μας είναι να ελαχιστοποιήσουμε τις δοκιμές
Όντως μοιάζει πολύ με το mastermind. Αλλά πιστεύω ότι σε ενδιαφέρει πιο πολύ επειδή θέλεις να το εφαρμόσεις στο λόττο ή κάτι τέτοιο. Το λόττο είναι ειδική περίπτωση του παραπάνω παιχνιδιού, όπου θέσαμε Ν=49 και Κ=6. Ζητείται ο ελάχιστος αριθμός στηλών που πρέπει να παίξουμε έτσι ώστε να εξασφαλίσουμε βέβαιο 5άρι
__________________________________________________________________
Συμβολίζω με Δ=Δ(Ν,Κ) το ελάχιστο πλήθος των δοκιμών που απαιτούνται. Αρχικά παρατηρούμε ότι Δ(Ν,Ν)=1 για κάθε Ν. Πραγματικά, αν από 5 αριθμούς ξέρουμε ότι έχουν επιλεγεί και οι 5, τότε απαιτείται μόνο μία δοκιμή (ομοίως θα μπορούσε να πει κάποιος ότι Δ(Ν,0)=1, δηλαδή στην περίπτωση κατά την οποία δεν έχει επιλεγεί κανείς αριθμός)
Έτσι λοιπόν έχει νόημα να ψάχνουμε το Δ(Ν,Κ) μόνο για Κ=1,2,3,...,Ν-1
Με τη βοήθεια του υπολογιστή έχω βρει ότι μάλλον υπάρχει μία συμμετρία ανάμεσα στις τιμές Δ(Ν,Κ) που έχουν ίδιο Ν
Συγκεκριμένα:
Για Ν=4 και για Κ=1,2,3 οι αντίστοιχες τιμές του Δ είναι 1,2,1
Για Ν=5 και για Κ=1,2,3,4 οι αντίστοιχες τιμές του Δ είναι 1,2,2,1
Για Ν=6 και για Κ=1,2,3,4,5 οι αντίστοιχες τιμές του Δ είναι 1,3,2,3,1
Και συγκεντρωτικά με το Ν να παίρνει τιμές από 2 μέχρι 8 τα παραπάνω αποτελέσματα φαίνονται στον πίνακα:
2: 1
3: 1 1
4: 1 2 1
5: 1 2 2 1
6: 1 3 2 3 1
7: 1 3 4 4 3 1
8: 1 4 5 6 5 4 1
Η "συμμετρία" που ανέφερα πιο πάνω περιγράφεται από τη σχέση Δ(Ν,Κ) = Δ(Ν,Ν-Κ)
Ίδια με τη συμμετρία που έχουν οι συνδυασμοί των Ν ανά Κ, δηλαδή C(N,K) = C(N,N-K)
Έχουμε λοιπόν συνδυασμούς των Ν αντικειμένων ανά Κ και θέλουμε να μαντέψουμε τουλάχιστον Κ-1 από τα Κ επιλεγμένα αντικείμενα. Σκοπός μας είναι να ελαχιστοποιήσουμε τις δοκιμές
Όντως μοιάζει πολύ με το mastermind. Αλλά πιστεύω ότι σε ενδιαφέρει πιο πολύ επειδή θέλεις να το εφαρμόσεις στο λόττο ή κάτι τέτοιο. Το λόττο είναι ειδική περίπτωση του παραπάνω παιχνιδιού, όπου θέσαμε Ν=49 και Κ=6. Ζητείται ο ελάχιστος αριθμός στηλών που πρέπει να παίξουμε έτσι ώστε να εξασφαλίσουμε βέβαιο 5άρι
__________________________________________________________________
Συμβολίζω με Δ=Δ(Ν,Κ) το ελάχιστο πλήθος των δοκιμών που απαιτούνται. Αρχικά παρατηρούμε ότι Δ(Ν,Ν)=1 για κάθε Ν. Πραγματικά, αν από 5 αριθμούς ξέρουμε ότι έχουν επιλεγεί και οι 5, τότε απαιτείται μόνο μία δοκιμή (ομοίως θα μπορούσε να πει κάποιος ότι Δ(Ν,0)=1, δηλαδή στην περίπτωση κατά την οποία δεν έχει επιλεγεί κανείς αριθμός)
Έτσι λοιπόν έχει νόημα να ψάχνουμε το Δ(Ν,Κ) μόνο για Κ=1,2,3,...,Ν-1
Με τη βοήθεια του υπολογιστή έχω βρει ότι μάλλον υπάρχει μία συμμετρία ανάμεσα στις τιμές Δ(Ν,Κ) που έχουν ίδιο Ν
Συγκεκριμένα:
Για Ν=4 και για Κ=1,2,3 οι αντίστοιχες τιμές του Δ είναι 1,2,1
Για Ν=5 και για Κ=1,2,3,4 οι αντίστοιχες τιμές του Δ είναι 1,2,2,1
Για Ν=6 και για Κ=1,2,3,4,5 οι αντίστοιχες τιμές του Δ είναι 1,3,2,3,1
Και συγκεντρωτικά με το Ν να παίρνει τιμές από 2 μέχρι 8 τα παραπάνω αποτελέσματα φαίνονται στον πίνακα:
2: 1
3: 1 1
4: 1 2 1
5: 1 2 2 1
6: 1 3 2 3 1
7: 1 3 4 4 3 1
8: 1 4 5 6 5 4 1
Η "συμμετρία" που ανέφερα πιο πάνω περιγράφεται από τη σχέση Δ(Ν,Κ) = Δ(Ν,Ν-Κ)
Ίδια με τη συμμετρία που έχουν οι συνδυασμοί των Ν ανά Κ, δηλαδή C(N,K) = C(N,N-K)
Σημείωση: Το μήνυμα αυτό γράφτηκε 16 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.
06-04-08
19:31
Γιώργο φαίνεται ότι είσαι πολύ προχωρημένος.. Πολύ ωραία η λύση σου στην άσκηση με το τρίγωνο!
Ασχολείσαι με διαγωνισμούς;
Ασχολείσαι με διαγωνισμούς;
Σημείωση: Το μήνυμα αυτό γράφτηκε 16 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.