Δύσκολο πρόβλημα με Λόττο

[axilmar]

Αν κάνω εργοδική ανάπτυξη το σύνολο των στηλών, τότε με τη συνθήκη "διαφορά ανά ζεύγος >= 3" θα μου κόψει ακριβώς 13803 στήλες (= τα 13545 τεσσάρια και τα 258 πεντάρια). Τελειώνει η εργοδική ανάπτυξη και έχω μία στήλη.
Για τη δεύτερη στήλη τώρα κάνω εργοδική ανάπτυξη πάλι με έξω τις 13804 (έξω δηλαδή οι κομμένες και έξω της πρώτης φάσης και η έξω η μία η χρησιμοποιούμενη), αλλά τώρα θα κόψει 13803 ; Παρακάτω ;
Όταν τελειώσουν όλες οι στήλες θα μου έχουν μείνει αρκετά περισσότερες από 1013.

Αν στη φάση που ψάχνω για τη δεύτερη στήλη τις κρατήσω κάπου δοκιμαστικά και κρατήσω σαν παιζόμενη στήλη αυτήν που κάνει τα μάξιμουμ κοψίματα ; Μήπως ; Και βγαίνει σε manageable χρόνο αυτό ;

Παρντον; κανενα παραδειγματακι;

[wooded glade]

Αν κάνω εργοδική ανάπτυξη το σύνολο των στηλών, τότε με τη συνθήκη "διαφορά ανά ζεύγος >= 3" θα μου κόψει ακριβώς 13803 στήλες (= τα 13545 τεσσάρια και τα 258 πεντάρια). Τελειώνει η εργοδική ανάπτυξη και έχω μία στήλη.
Για τη δεύτερη στήλη τώρα κάνω εργοδική ανάπτυξη πάλι με έξω τις 13804 (έξω δηλαδή οι κομμένες και έξω της πρώτης φάσης και η έξω η μία η χρησιμοποιούμενη), αλλά τώρα θα κόψει 13803 ; Παρακάτω ;
Όταν τελειώσουν όλες οι στήλες θα μου έχουν μείνει αρκετά περισσότερες από 1013.

Αν στη φάση που ψάχνω για τη δεύτερη στήλη τις κρατήσω κάπου δοκιμαστικά και κρατήσω σαν παιζόμενη στήλη αυτήν που κάνει τα μάξιμουμ κοψίματα ; Μήπως ; Και βγαίνει σε manageable χρόνο αυτό ;

Παρντον; κανενα παραδειγματακι;

Η πρώτη στήλη του αναπτύγματος μου είναι η 1-2-3-4-5-6.
Αυτή κόβει 13803 ακριβώς.
'Οταν πάω για τη δεύτερη ξεκινάω με 1-2-3-7-8-9 αλλά πόσες θα κόψει αυτή ; Μετά η 1-2-3-10-11-12 ας πούμε πόσες ; 13803 πάλι ή λιγώτερες ;
Κάποια όμως από τις 13983816 - 133804 εναπομείνασες θα κόβει μάξιμουμ. Αυτή λοιπόν να είναι η 2η στήλη μου και γενικώς η (Ν+1)η όταν έχω βρει Ν στήλες.
Μπορεί να βγει έτσι.
Αλλά μήπως αυτός ο τρόπος είναι ένας από αυτούς που έχω δοκιμάσει ; Δεν θυμάμαι τώρα - έχουν περάσει χρόνια.
Μήπως δεν το έχω δοκιμάσει επειδή δεν μπορούσαν να το αντέξουν τα παλιά pc ;
Μπορώ πάντως να το κάνω με 15-16 νούμερα (να κάνω D15, D16 δλδ) και βλέπουμε.

(*) κάνας άλλος που το παίζει επαϊων ; O yochanan που είναι ;

[axilmar]

Αν κάνω εργοδική ανάπτυξη το σύνολο των στηλών, τότε με τη συνθήκη "διαφορά ανά ζεύγος >= 3" θα μου κόψει ακριβώς 13803 στήλες (= τα 13545 τεσσάρια και τα 258 πεντάρια). Τελειώνει η εργοδική ανάπτυξη και έχω μία στήλη.
Για τη δεύτερη στήλη τώρα κάνω εργοδική ανάπτυξη πάλι με έξω τις 13804 (έξω δηλαδή οι κομμένες και έξω της πρώτης φάσης και η έξω η μία η χρησιμοποιούμενη), αλλά τώρα θα κόψει 13803 ; Παρακάτω ;
Όταν τελειώσουν όλες οι στήλες θα μου έχουν μείνει αρκετά περισσότερες από 1013.

Αν στη φάση που ψάχνω για τη δεύτερη στήλη τις κρατήσω κάπου δοκιμαστικά και κρατήσω σαν παιζόμενη στήλη αυτήν που κάνει τα μάξιμουμ κοψίματα ; Μήπως ; Και βγαίνει σε manageable χρόνο αυτό ;

Παρντον; κανενα παραδειγματακι;

Η πρώτη στήλη του αναπτύγματος μου είναι η 1-2-3-4-5-6.
Αυτή κόβει 13803 ακριβώς.
'Οταν πάω για τη δεύτερη ξεκινάω με 1-2-3-7-8-9 αλλά πόσες θα κόψει αυτή ; Μετά η 1-2-3-10-11-12 ας πούμε πόσες ; 13803 πάλι ή λιγώτερες ;
Κάποια όμως από τις 13983816 - 133804 εναπομείνασες θα κόβει μάξιμουμ. Αυτή λοιπόν να είναι η 2η στήλη μου και γενικώς η (Ν+1)η όταν έχω βρει Ν στήλες.
Μπορεί να βγει έτσι.
Αλλά μήπως αυτός ο τρόπος είναι ένας από αυτούς που έχω δοκιμάσει ; Δεν θυμάμαι τώρα - έχουν περάσει χρόνια.
Μήπως δεν το έχω δοκιμάσει επειδή δεν μπορούσαν να το αντέξουν τα παλιά pc ;
Μπορώ πάντως να το κάνω με 15-16 νούμερα (να κάνω D15, D16 δλδ) και βλέπουμε.

(*) κάνας άλλος που το παίζει επαϊων ; O yochanan που είναι ;

Εννοειται, αμα κοβεις στηλες θα μειωθει ο αριθμος των περιπτωσεων, αλλα και παλι NP complete ειναι το προβλημα...πχ το 10000 choose 1000 το γοογκλε το βγαζει undefined.

To 10000 choose 100 εχει αποτελεσμα 6.520847e+241, δλδ 241 ψηφια.

[wooded glade]

Παρντον; κανενα παραδειγματακι;

Η πρώτη στήλη του αναπτύγματος μου είναι η 1-2-3-4-5-6.
Αυτή κόβει 13803 ακριβώς.
'Οταν πάω για τη δεύτερη ξεκινάω με 1-2-3-7-8-9 αλλά πόσες θα κόψει αυτή ; Μετά η 1-2-3-10-11-12 ας πούμε πόσες ; 13803 πάλι ή λιγώτερες ;
Κάποια όμως από τις 13983816 - 133804 εναπομείνασες θα κόβει μάξιμουμ. Αυτή λοιπόν να είναι η 2η στήλη μου και γενικώς η (Ν+1)η όταν έχω βρει Ν στήλες.
Μπορεί να βγει έτσι.
Αλλά μήπως αυτός ο τρόπος είναι ένας από αυτούς που έχω δοκιμάσει ; Δεν θυμάμαι τώρα - έχουν περάσει χρόνια.
Μήπως δεν το έχω δοκιμάσει επειδή δεν μπορούσαν να το αντέξουν τα παλιά pc ;
Μπορώ πάντως να το κάνω με 15-16 νούμερα (να κάνω D15, D16 δλδ) και βλέπουμε.

(*) κάνας άλλος που το παίζει επαϊων ; O yochanan που είναι ;

Εννοειται, αμα κοβεις στηλες θα μειωθει ο αριθμος των περιπτωσεων, αλλα και παλι NP complete ειναι το προβλημα...πχ το 10000 choose 1000 το γοογκλε το βγαζει undefined.

To 10000 choose 100 εχει αποτελεσμα 6.520847e+241, δλδ 241 ψηφια.

Πάντα κόβω. Λέμε να κόβω μάξιμουμ ώστε το τελικό εξαγόμενο να είναι μίνιμουμ.
Εσύ πας να πάρεις όλα τα υποσύνολα των 13983816 στηλών και να τα ελέγξεις που δεν γίνεται με τίποτα αλλά επίσης το 1013 είναι ένα θεωρητικό νούμερο - το περίπου ας πούμε. Δεν ξέρεις ότι είναι μόνο τα υποσύνολα των 1013 στηλών αυτά που θες.

[axilmar]

Η πρώτη στήλη του αναπτύγματος μου είναι η 1-2-3-4-5-6.
Αυτή κόβει 13803 ακριβώς.
'Οταν πάω για τη δεύτερη ξεκινάω με 1-2-3-7-8-9 αλλά πόσες θα κόψει αυτή ; Μετά η 1-2-3-10-11-12 ας πούμε πόσες ; 13803 πάλι ή λιγώτερες ;
Κάποια όμως από τις 13983816 - 133804 εναπομείνασες θα κόβει μάξιμουμ. Αυτή λοιπόν να είναι η 2η στήλη μου και γενικώς η (Ν+1)η όταν έχω βρει Ν στήλες.
Μπορεί να βγει έτσι.
Αλλά μήπως αυτός ο τρόπος είναι ένας από αυτούς που έχω δοκιμάσει ; Δεν θυμάμαι τώρα - έχουν περάσει χρόνια.
Μήπως δεν το έχω δοκιμάσει επειδή δεν μπορούσαν να το αντέξουν τα παλιά pc ;
Μπορώ πάντως να το κάνω με 15-16 νούμερα (να κάνω D15, D16 δλδ) και βλέπουμε.

(*) κάνας άλλος που το παίζει επαϊων ; O yochanan που είναι ;

Εννοειται, αμα κοβεις στηλες θα μειωθει ο αριθμος των περιπτωσεων, αλλα και παλι NP complete ειναι το προβλημα...πχ το 10000 choose 1000 το γοογκλε το βγαζει undefined.

To 10000 choose 100 εχει αποτελεσμα 6.520847e+241, δλδ 241 ψηφια.

Πάντα κόβω. Λέμε να κόβω μάξιμουμ ώστε το τελικό εξαγόμενο να είναι μίνιμουμ.
Εσύ πας να πάρεις όλα τα υποσύνολα των 13983816 στηλών και να τα ελέγξεις που δεν γίνεται με τίποτα αλλά επίσης το 1013 είναι ένα θεωρητικό νούμερο - το περίπου ας πούμε. Δεν ξέρεις ότι είναι μόνο τα υποσύνολα των 1013 στηλών αυτά που θες.

10000 choose 100 = 6.520847e+241

Κοψε οτι θες, αλλα εαν δεν φτασεις σε πολυ πολυ μικρα νουμερα, δεν βρισκεις ακρη.

[wooded glade]

Εννοειται, αμα κοβεις στηλες θα μειωθει ο αριθμος των περιπτωσεων, αλλα και παλι NP complete ειναι το προβλημα...πχ το 10000 choose 1000 το γοογκλε το βγαζει undefined.

To 10000 choose 100 εχει αποτελεσμα 6.520847e+241, δλδ 241 ψηφια.

Πάντα κόβω. Λέμε να κόβω μάξιμουμ ώστε το τελικό εξαγόμενο να είναι μίνιμουμ.
Εσύ πας να πάρεις όλα τα υποσύνολα των 13983816 στηλών και να τα ελέγξεις που δεν γίνεται με τίποτα αλλά επίσης το 1013 είναι ένα θεωρητικό νούμερο - το περίπου ας πούμε. Δεν ξέρεις ότι είναι μόνο τα υποσύνολα των 1013 στηλών αυτά που θες.

10000 choose 100 = 6.520847e+241

Κοψε οτι θες, αλλα εαν δεν φτασεις σε πολυ πολυ μικρα νουμερα, δεν βρισκεις ακρη.

Δν έχω χρόνο αυτή τη στιγμή να δοκιμάσω αυτό που είπα - αργότερα.
Αλλά κάποιος άλλος φλούφλης μπορεί ; Εξήγησα ένα σχέδιο.

[wooded glade]

Μου φαίνεται ότι η μέθοδος που προτείνω είναι πολύ αργή για τα 49 νούμερα.
Ας πούμε ξεκινάω με τη στήλη 1-2-3-4-5-6 σαν παιζόμενη στήλη.
Αυτή θα κόβει 13803 ακριβώς, κάνω την εργοδική ανάπτυξη των 49 αριθμών, τσεκάρω τις κομένες καθώς και την 1-2-3-4-5-6 σαν ήδη χρησιμοποιημένη.
Πάω μετά για τη δεύτερη. Λογικά θα βρω να κόβει πάλι 13803 αλλά θα είναι πολλές τέτοιες (η 44-45-46-47-48-49 π.χ. ή η 20-21-22-23-24-25). Ερώτημα πρώτον: Είναι όλες αυτές ισοδύναμες ως προς το τελικό ζητούμενο, να βγει μίνιμουμ το τελικό αποτέλεσμα δηλαδή ;
Αλλά παρακάτω ας πούμε η νι-οστή στήλη που βρίσκω κόβει 12,500 μόνο. Πρέπει να συνεχίσω την εργοδική ανάπτυξη ως το τέλος και να πάρω σαν παιζόμενη στήλη αυτή που κόβει τα πιό πολλά, 12510 ας πούμε (που και πάλι δεν είναι σίγουρο).
Πάει μακρυά, μου φαίνεται σαν να χρειάζονται 14 εκατομμύρια στο τετράγωνο φορές να γίνει η εργοδική ανάπτυξη και η κάθε εργοδική ανάπτυξη θέλει κάποια δευτερόλεπτα βέβαια.

Φυσικά αν παίρνω τις στήλες που διαφέρουν 3 και άνω από την κάθε ήδη παιζόμενη με μία απλή εργοδική ανάπτυξη, είναι αποτυχία.
Το ίδιο και αν πάω κατά στάδια: Να διαφέρουν κατά 6, μετά κατά 5, μετά κατά 4, μετά κατά 3 - αποτυγχάνει.

[NoMoreLice]

Θεωρητικά ο αριθμός στηλών για να επιτυγχάνεται το 4άρι είναι 1013.
Πως προκύπτει αυτό ;
Αν η στήλη μου είναι η 1-2-3-4-5-6 τότε αυτή σαν νικήτρια στήλη πιάνει 1 εξάρι, 6 πεντάρια (6 choose 5 = 6) και 15 τεσσάρια (6 choose 4 = 15).
Αλλά για τα έξη πεντάρια υπάρχουν 258 άλλες στήλες που έχουν τα ίδιο πεντάρια (6 χ (43 choose 1) = 258).
Και για τα 15 τεσσάρια της εξάδας μου υπάρχουν 13545 στήλες που έχουν τα ίδια τεσσάρια (15 χ (43 choose 2) = 13545).
΄
Άρα το σύνολο των 13983816 στηλών προκειμένου για "ένα τεσσάρι και άνω" γίνεται 13983816 / (1 + 258 + 13545) = 1013.026.

Νομίζω πως κάνεις λάθος, διότι με τη διαίρεση είναι σαν να θεωρείς πως κάθε στήλη διαθέτει τα δικά της αποκλειστικά 4αρια. Για να το δεις παρε το απλό παράδειγμα όπου θες να βρεις τα 6 νούμερα από το 1 ως το 11. Με τον τρόπο που είπες έχουμε:

-11 ανά 6 = 462 πιθανές στηλες
-1 6άρι
-6 * (5 ανά 2) = 60 5άρια
-15 * (5 ανά 2) = 150 4άρια

Άρα, αν πάμε με τη διαίρεση, υπάρχουν 462/(1+60+150) = 2.18 (βάλε 3) στήλες που μπορούν να μας εγγυηθούν 4άρι.

Αν μου βρεις 3 στήλες που το κάνουν αυτό θα παραδεχθώ ότι έχεις δίκιο.
Και 4 και 5 αν βρεις πάλι πες το, γιατί εγώ το ελάχιστο που βρίσκω με ένα απλό προγραμματάκι που έκανα είναι 6.

[wooded glade]

Θεωρητικά ο αριθμός στηλών για να επιτυγχάνεται το 4άρι είναι 1013.
Πως προκύπτει αυτό ;
Αν η στήλη μου είναι η 1-2-3-4-5-6 τότε αυτή σαν νικήτρια στήλη πιάνει 1 εξάρι, 6 πεντάρια (6 choose 5 = 6) και 15 τεσσάρια (6 choose 4 = 15).
Αλλά για τα έξη πεντάρια υπάρχουν 258 άλλες στήλες που έχουν τα ίδιο πεντάρια (6 χ (43 choose 1) = 258).
Και για τα 15 τεσσάρια της εξάδας μου υπάρχουν 13545 στήλες που έχουν τα ίδια τεσσάρια (15 χ (43 choose 2) = 13545).
΄
Άρα το σύνολο των 13983816 στηλών προκειμένου για "ένα τεσσάρι και άνω" γίνεται 13983816 / (1 + 258 + 13545) = 1013.026.

Νομίζω πως κάνεις λάθος, διότι με τη διαίρεση είναι σαν να θεωρείς πως κάθε στήλη διαθέτει τα δικά της αποκλειστικά 4αρια. Για να το δεις παρε το απλό παράδειγμα όπου θες να βρεις τα 6 νούμερα από το 1 ως το 11. Με τον τρόπο που είπες έχουμε:

-11 ανά 6 = 462 πιθανές στηλες
-1 6άρι
-6 * (5 ανά 2) = 60 5άρια
-15 * (5 ανά 2) = 150 4άρια

Άρα, αν πάμε με τη διαίρεση, υπάρχουν 462/(1+60+150) = 2.18 (βάλε 3) στήλες που μπορούν να μας εγγυηθούν 4άρι.

Αν μου βρεις 3 στήλες που το κάνουν αυτό θα παραδεχθώ ότι έχεις δίκιο.
Και 4 και 5 αν βρεις πάλι πες το, γιατί εγώ το ελάχιστο που βρίσκω με ένα απλό προγραμματάκι που έκανα είναι 6.

Όλα αυτά τα είχα σε δισκέτες MS DOS !
Θα το κοιτάξω.
Αλλά το link που γράφω πιό πάνω τι λέει για 4 στα 6 στους 11 αριθμούς ;

[NoMoreLice]

Θεωρητικά ο αριθμός στηλών για να επιτυγχάνεται το 4άρι είναι 1013.
Πως προκύπτει αυτό ;
Αν η στήλη μου είναι η 1-2-3-4-5-6 τότε αυτή σαν νικήτρια στήλη πιάνει 1 εξάρι, 6 πεντάρια (6 choose 5 = 6) και 15 τεσσάρια (6 choose 4 = 15).
Αλλά για τα έξη πεντάρια υπάρχουν 258 άλλες στήλες που έχουν τα ίδιο πεντάρια (6 χ (43 choose 1) = 258).
Και για τα 15 τεσσάρια της εξάδας μου υπάρχουν 13545 στήλες που έχουν τα ίδια τεσσάρια (15 χ (43 choose 2) = 13545).
΄
Άρα το σύνολο των 13983816 στηλών προκειμένου για "ένα τεσσάρι και άνω" γίνεται 13983816 / (1 + 258 + 13545) = 1013.026.

Νομίζω πως κάνεις λάθος, διότι με τη διαίρεση είναι σαν να θεωρείς πως κάθε στήλη διαθέτει τα δικά της αποκλειστικά 4αρια. Για να το δεις παρε το απλό παράδειγμα όπου θες να βρεις τα 6 νούμερα από το 1 ως το 11. Με τον τρόπο που είπες έχουμε:

-11 ανά 6 = 462 πιθανές στηλες
-1 6άρι
-6 * (5 ανά 2) = 60 5άρια
-15 * (5 ανά 2) = 150 4άρια

Άρα, αν πάμε με τη διαίρεση, υπάρχουν 462/(1+60+150) = 2.18 (βάλε 3) στήλες που μπορούν να μας εγγυηθούν 4άρι.

Αν μου βρεις 3 στήλες που το κάνουν αυτό θα παραδεχθώ ότι έχεις δίκιο.
Και 4 και 5 αν βρεις πάλι πες το, γιατί εγώ το ελάχιστο που βρίσκω με ένα απλό προγραμματάκι που έκανα είναι 6.

Όλα αυτά τα είχα σε δισκέτες MS DOS !
Θα το κοιτάξω.
Αλλά το link που γράφω πιό πάνω τι λέει για 4 στα 6 στους 11 αριθμούς ;

5 λέει.

[wooded glade]

Νομίζω πως κάνεις λάθος, διότι με τη διαίρεση είναι σαν να θεωρείς πως κάθε στήλη διαθέτει τα δικά της αποκλειστικά 4αρια. Για να το δεις παρε το απλό παράδειγμα όπου θες να βρεις τα 6 νούμερα από το 1 ως το 11. Με τον τρόπο που είπες έχουμε:

-11 ανά 6 = 462 πιθανές στηλες
-1 6άρι
-6 * (5 ανά 2) = 60 5άρια
-15 * (5 ανά 2) = 150 4άρια

Άρα, αν πάμε με τη διαίρεση, υπάρχουν 462/(1+60+150) = 2.18 (βάλε 3) στήλες που μπορούν να μας εγγυηθούν 4άρι.

Αν μου βρεις 3 στήλες που το κάνουν αυτό θα παραδεχθώ ότι έχεις δίκιο.
Και 4 και 5 αν βρεις πάλι πες το, γιατί εγώ το ελάχιστο που βρίσκω με ένα απλό προγραμματάκι που έκανα είναι 6.

Όλα αυτά τα είχα σε δισκέτες MS DOS !
Θα το κοιτάξω.
Αλλά το link που γράφω πιό πάνω τι λέει για 4 στα 6 στους 11 αριθμούς ;

5 λέει.

Επειδή τα 11 νούμερα είναι λίγα πιστεύω αυτό θα είναι το μίνιμουμ, με κάποιο βαζιβουζουκικό τρόπο θα έκοψε άλλη μία στήλη από τις 6 που λες εσύ.
Τα δικά μου είναι σε δισκέτες dos από τα παλιά χρόνια, πρέπει να κάνω ανασκαφές και να βρω disk drive.
Είχαμε κι ένα downloadable πρόγραμμα windows με συστηματάκια μέσα καλό στα Γερμανικά αλλά κάηκε (!) το computer.
Δεν ξέρω πάντως αν υπάρχει γενική λύση.
Δεν είπα ότι το απόλυτο μίνιμουμ που βγαίνει με τη διαίρεση είναι υλοποιήσιμο, είπα ότι είναι το "ιδανικό όριο".

[NoMoreLice]

Όλα αυτά τα είχα σε δισκέτες MS DOS !
Θα το κοιτάξω.
Αλλά το link που γράφω πιό πάνω τι λέει για 4 στα 6 στους 11 αριθμούς ;

5 λέει.

Επειδή τα 11 νούμερα είναι λίγα πιστεύω αυτό θα είναι το μίνιμουμ, με κάποιο βαζιβουζουκικό τρόπο θα έκοψε άλλη μία στήλη από τις 6 που λες εσύ.
Τα δικά μου είναι σε δισκέτες dos από τα παλιά χρόνια, πρέπει να κάνω ανασκαφές και να βρω disk drive.
Είχαμε κι ένα downloadable πρόγραμμα windows με συστηματάκια μέσα καλό στα Γερμανικά αλλά κάηκε (!) το computer.
Δεν ξέρω πάντως αν υπάρχει γενική λύση.
Δεν είπα ότι το απόλυτο μίνιμουμ που βγαίνει με τη διαίρεση είναι υλοποιήσιμο, είπα ότι είναι το "ιδανικό όριο".

Ωπ, μάλλον ναι, βρήκα με 5 λογικά (ξεκινώντας από το 0, δηλ. αριθμοί από 0 ως και το 10):

[0, 3, 4, 5, 7, 9]
[0, 1, 2, 8, 9, 10]
[1, 2, 5, 7, 8, 10]
[3, 4, 6, 8, 9, 10]
[0, 1, 2, 3, 4, 6]

Edit: και για αριθμούς από 0 ως 11 βρήκα με 6 στήλες όπως λέει στο site, οπότε τείνω να πιστέψω ότι σωστοί είναι οι αριθμοί που έχει:
[0, 2, 4, 5, 7, 11]
[3, 4, 5, 6, 8, 11]
[0, 1, 3, 7, 9, 10]
[0, 1, 2, 3, 6, 8]
[2, 6, 7, 8, 9, 10]
[1, 4, 5, 9, 10, 11]