Καραμέλες σε κουτιά

Συντονιστές: Demetres, silouan

panagiotis99
Δημοσιεύσεις: 133
Εγγραφή: Δευ Φεβ 04, 2013 8:24 pm
Τοποθεσία: Αθηνα

Καραμέλες σε κουτιά

#1

Μη αναγνωσμένη δημοσίευση από panagiotis99 » Σάβ Φεβ 25, 2017 6:09 pm

Καλησπέρα, μιας και ο Αρχιμήδης πλησιάζει προτείνω το παρακάτω, ελπίζοντας να ταυτίζεται με το επίπεδο του.

Σε n \geq 4 κουτιά υπάρχουν (συνολικά) τουλάχιστον 4 καραμέλες. Kάθε φορά ο Νίκος επιτρέπεται να διαλέξει 2 κουτιά και να πάρει μία καραμέλα από το καθένα και να τις βάλει σε ένα τρίτο κουτί. Να εξετάσετε για ποια n είναι πιθανό να βάλει όλες τις καραμέλες σε ένα κουτί.
τελευταία επεξεργασία από panagiotis99 σε Σάβ Φεβ 25, 2017 7:51 pm, έχει επεξεργασθεί 1 φορά συνολικά.



Λέξεις Κλειδιά:
mikemoke
Δημοσιεύσεις: 200
Εγγραφή: Σάβ Δεκ 17, 2016 12:58 am

Re: Μπάλες σε κουτιά

#2

Μη αναγνωσμένη δημοσίευση από mikemoke » Σάβ Φεβ 25, 2017 7:49 pm

panagiotis99 έγραψε:Καλησπέρα, μιας και ο Αρχιμήδης πλησιάζει προτείνω το παρακάτω, ελπίζοντας να ταυτίζεται με το επίπεδο του.

Σε n \geq 4 κουτιά υπάρχουν (συνολικά) τουλάχιστον 4 καραμέλες. Kάθε φορά ο Νίκος επιτρέπεται να διαλέξει 2 κουτιά και να πάρει μία καραμέλα από το καθένα και να τις βάλει σε ένα τρίτο κουτί. Να εξετάσετε για ποια n είναι πιθανό να βάλει όλες τις καραμέλες σε ένα κουτί.
Το
τελευταία επεξεργασία από mikemoke σε Κυρ Φεβ 26, 2017 3:56 pm, έχει επεξεργασθεί 1 φορά συνολικά.


mikemoke
Δημοσιεύσεις: 200
Εγγραφή: Σάβ Δεκ 17, 2016 12:58 am

Re: Καραμέλες σε κουτιά

#3

Μη αναγνωσμένη δημοσίευση από mikemoke » Σάβ Φεβ 25, 2017 8:08 pm

panagiotis99 έγραψε:Καλησπέρα, μιας και ο Αρχιμήδης πλησιάζει προτείνω το παρακάτω, ελπίζοντας να ταυτίζεται με το επίπεδο του.

Σε n \geq 4 κουτιά υπάρχουν (συνολικά) τουλάχιστον 4 καραμέλες. Kάθε φορά ο Νίκος επιτρέπεται να διαλέξει 2 κουτιά και να πάρει μία καραμέλα από το καθένα και να τις βάλει σε ένα τρίτο κουτί. Να εξετάσετε για ποια n είναι πιθανό να βάλει όλες τις καραμέλες σε ένα κουτί.
]
τελευταία επεξεργασία από mikemoke σε Κυρ Φεβ 26, 2017 3:56 pm, έχει επεξεργασθεί 1 φορά συνολικά.


panagiotis99
Δημοσιεύσεις: 133
Εγγραφή: Δευ Φεβ 04, 2013 8:24 pm
Τοποθεσία: Αθηνα

Re: Μπάλες σε κουτιά

#4

Μη αναγνωσμένη δημοσίευση από panagiotis99 » Σάβ Φεβ 25, 2017 9:05 pm

mikemoke έγραψε: Το τρίτο κουτί πρέπει να αλλάζει ή είναι σταθερό
To τρίτο κουτί είναι τυχαίο.
mikemoke έγραψε: Το ζητούμενο μπορεί να επιτευχθεί για οποιοδήποτεn. Αν τοποθετήσουμε των απαραίτητο αριθμό καραμέλων κατάλληλα στα κουτιά
Ο αριθμός των καραμελών είναι τυχαίος και έχουν τοποθετηθεί τυχαία στα κουτιά.


Ξαναδιαβάστε πιο προσεκτικά την εκφώνηση.

Παναγιώτης.


mikemoke
Δημοσιεύσεις: 200
Εγγραφή: Σάβ Δεκ 17, 2016 12:58 am

Re: Μπάλες σε κουτιά

#5

Μη αναγνωσμένη δημοσίευση από mikemoke » Σάβ Φεβ 25, 2017 11:24 pm

[quote="panagiotis99"][quote="mikemoke"]
Το\ο
τελευταία επεξεργασία από mikemoke σε Κυρ Φεβ 26, 2017 3:56 pm, έχει επεξεργασθεί 1 φορά συνολικά.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7884
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Καραμέλες σε κουτιά

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Φεβ 25, 2017 11:57 pm

mikemoke χρειάζεται περισσότερη προσοχή σε αυτά που γράφεις. Και εδώ αλλά και σε άλλες ασκήσεις νομίζω πως βιάζεσαι να απαντήσεις.

Πρέπει να μπορέσεις να φέρεις τις καραμέλες σε ένα κουτί ξεκινώντας από οποιαδήποτε διάταξη καραμελών. Ας πιάσουμε ένα συγκεκριμένο παράδειγμα εδώ. Έστω ότι τα κουτιά έχουν 4,1,0,0 καραμέλες. Πως θα τις βάλεις όλες στο ίδιο κουτί; Μπορεί να γίνει αλλά το «βάζω τις καραμέλες σε ένα τρίτο κουτί σταθερό» είναι αρκετά ασαφές.


panagiotis99
Δημοσιεύσεις: 133
Εγγραφή: Δευ Φεβ 04, 2013 8:24 pm
Τοποθεσία: Αθηνα

Re: Καραμέλες σε κουτιά

#7

Μη αναγνωσμένη δημοσίευση από panagiotis99 » Πέμ Μαρ 02, 2017 3:48 pm

Επαναφορά!(Μιας και ο Αρχιμήδης πλησιάζει)


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7884
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Καραμέλες σε κουτιά

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Μαρ 02, 2017 4:57 pm

Θα δείξουμε ότι αυτό γίνεται για όλα τα n. Μπορώ να υποθέσω ότι αρχικά δεν βρίσκονται όλες οι καραμέλες στο ίδιο κουτί.

Λήμμα 1: Αν κάποιο κουτί έχει τουλάχιστον δύο καραμέλες, τότε στα υπόλοιπα κουτιά μπορώ να μετακινήσω τις καραμέλες όπως θέλω.

Απόδειξη: Έστω ότι έχω αρχικά a,b,c,d καραμέλες στα κουτιά με a \geqslant 2. Έστω ότι θέλω να μεταφέρω μία καραμέλα από το κουτί με b καραμέλες στο κουτί με d καραμέλες. Αυτό μπορώ να το επιτύχω ως εξής:

Κίνηση 1η: a-1,b-1,c+2,d
Κίνηση 2η: a-2,b-1,c+1,d+2
Κίνηση 3η: a,b-1,c,d+1

Λήμμα 2: Αν κάποιο κουτί έχει τουλάχιστον δύο καραμέλες, τότε μπορώ να φύγω μία καραμέλα από αυτό και να την μετακινήσω σε ένα κουτί που έχει τουλάχιστον μία καραμέλα.

Απόδειξη: Έστω ότι έχω αρχικά a,b,c,d καραμέλες στα κουτιά με a \geqslant 2. Έστω ότι θέλω να μεταφέρω μία καραμέλα από το κουτί με a καραμέλες στο κουτί με b καραμέλες όπου b \geqslant 1. Αυτό μπορώ να το επιτύχω ως εξής:

Κίνηση 1η: a-1,b-1,c+2,d
Κίνηση 2η: a-2,b-1,c+1,d+2
Κίνηση 3η: a,b-1,c,d+1
Κίνηση 4η: a-1,b+1,c,d

\rule{500pt}{0.6pt}

Πάμε τώρα στην άσκηση. Μπορώ να υποθέσω ότι δεν είναι όλες οι καραμέλες στο ίδιο κουτί. (Αφού αλλιώς δεν χρειάζεται να κάνω κάτι.) Μπορώ επίσης να υποθέσω ότι υπάρχει κουτί με τουλάχιστον δύο καραμέλες. (Αν όχι τότε αρχικά έχουμε τέσσερις καραμέλες με μία καραμέλα σε κάθε κουτί. Στην επόμενη κίνηση όμως μπορώ να έχω κουτί με τουλάχιστον δύο καραμέλες.)

Έστω n=2m άρτιος. Χρησιμοποιώντας το Λήμμα 1 μπορώ να αφήσω καραμέλες σε μόνο δύο κουτιά, έστω τα πρώτα δύο, με το πρώτο να έχει τουλάχιστον τόσες καραμέλες όσες το δεύτερο. Τότε το πρώτο κουτί έχει τουλάχιστον m \geqslant 2 καραμέλες. Χρησιμοποιώντας το Λήμμα 2 μεταφέρω καραμέλες από το πρώτο στο δεύτερο κουτί ώστε να καταλήξω με m καραμέλες σε κάθε ένα από αυτά τα δύο κουτιά. Τώρα παίρνω μία καραμέλα από κάθε ένα από αυτά και τις βάζω στο τρίτο κουτί. Επαναλαμβάνοντας, όλες οι καραμέλες θα μεταφερθούν στο τρίτο κουτί.

Έστω n=2m+1 περιττός. Χρησιμοποιώντας το Λήμμα 1 μπορώ να αφήσω καραμέλες τις 2m καραμέλες σε μόνο δύο κουτιά, έστω τα πρώτα δύο, με το πρώτο να έχει τουλάχιστον τόσες καραμέλες όσες το δεύτερο, και την άλλη καραμέλα σε ένα άλλο κουτί, έστω το τρίτο. Τότε το πρώτο κουτί έχει τουλάχιστον m \geqslant 2 καραμέλες. Χρησιμοποιώντας το Λήμμα 2 μεταφέρω καραμέλες από το πρώτο στο δεύτερο κουτί ώστε να καταλήξω με m καραμέλες σε κάθε ένα από αυτά τα δύο κουτιά. Τώρα παίρνω μία καραμέλα από κάθε ένα από αυτά και τις βάζω στο τρίτο κουτί. Επαναλαμβάνοντας, όλες οι καραμέλες θα μεταφερθούν στο τρίτο κουτί.

Η μόνη περίπτωση να μην δουλεύει το πιο πάνω είναι να έχω 2m,0,1,0 καραμέλες. Τότε όμως στο επόμενο βήμα μπορώ να έχω 2m-1,2,0,0 καραμέλες και στο μεθεπόμενο 2m-2,1,2,0 ή ισοδύναμα 2m-2,2,1,0. Τότε όμως μπορώ να επαναλάβω την προηγούμενη παράγραφο αφού 2m-2 \geqsalnt 2.


panagiotis99
Δημοσιεύσεις: 133
Εγγραφή: Δευ Φεβ 04, 2013 8:24 pm
Τοποθεσία: Αθηνα

Re: Καραμέλες σε κουτιά

#9

Μη αναγνωσμένη δημοσίευση από panagiotis99 » Πέμ Μαρ 02, 2017 9:39 pm

Καλησπέρα Κύριε Δημήτρη ευχαριστώ για την ενασχόληση σας! :D
Λίγο διαφορετικά απο την δική σας προσέγγιση

Θα αποδείξω ότι ισχύει για κάθε n
Θα κάνω επαγωγή στο αριθμό των καραμελών έστω c. Αρχικά για c=4, υπάρχουν το πολύ 4 κουτία με καραμέλες.
Οι πιθανές θέσεις των καραμελών στα μη άδεια κουτιά είναι:
(1,1,1,1),(1,1,2,0),(2,2,0,0),(1,3,0,0),(4,0,0,0)

Για την πρώτη πιθανότητα έχουμε: (1,1,1,1) -> (1,3,0,0) -> (2,0,2,0) -> (1,0,1,2) -> (0,0,0,4).
Άρα είναι δυνατό να βάλουμε όλες τις καραμέλες σε ένα κουτί για την πρώτη πιθανότητα. Παρατηρούμε ότι όλες οι άλλες πιθανότητες διαμέρισης εμφανίζονται στην παραπάνω διαδικασία.

Υποθέτουμε ότι είναι δυνατό για κάποιο c αρκεί να δείξω ότι είναι δυνατο για c+1 καραμέλες.
Από την επαγωγική υπόθεση έχουμε αποδείξει ότι γίνεται να βάλουμε c καραμέλες σε ένα κουτί.
Αν το κουτί περιέχει και την άλλη καραμέλα τότε τελειώσαμε.
Αν η άλλη καραμέλα είναι σε ένα άλλο κουτί τότε κάνουμε το εξής.
Επιλέγουμε δύο κενα κουτιά (σίγουρα υπάρχουν) και τα κουτία με τις c καραμέλες και με την μία καραμέλα και ακολοθούμε την ακόλουθη διαδικασία.
(1,c,0,0)->(0,c-1,2,0)->(0,c-2,1,2) ->(2,c-3,0,2)->(1,c-1,0,1)->(0,c+1,0,0)


Απάντηση

Επιστροφή σε “Συνδυαστική - Επίπεδο Αρχιμήδη (Seniors)”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης