Προβλήματα Μαθηματικών

20 Οκτωβρίου, 2009

Διπλασιασμός μέχρι τέλους

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 12:12 πμ

Τρείς φίλοι ξεκινούν έχοντας ένα (ακέραιο, θετικό) χρηματικό ποσό ο καθένας.

Σε κάθε βήμα δύο από αυτούς μπορούν να τροποποιούν τα ποσά που έχουν ως εξής:

αν είναι x\le y τα δύο ποσά τότε αυτός που έχει τα περισσότερα δίνει στον άλλο όσα έχει ο άλλος. Τα δύο ποσά γίνονται δηλ. 2x και y-x.

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

17 Σχόλια »

  1. Οι ανταλλαγές γίνονται σε τυχαία σειρά ή πχ πρώτα ο Α με τον Β, μετά ο Β με τον Γ, μετά ο Γ με τον Α κοκ?

    Μου αρέσει!

    Σχόλιο από nefelh — 21 Οκτωβρίου, 2009 @ 2:06 μμ

  2. Όπως αυτοί θέλουν ώστε να πετύχουν το σκοπό τους.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 21 Οκτωβρίου, 2009 @ 2:32 μμ

  3. Υπόδειξη:

    Θεωρείστε δύο άτομα από τα τρία μόνο και υποθέστε ότι ο ένας έχει περιττό ποσό και ο άλλος άρτιο. Δείξτε ότι αυτός που έχει το άρτιο ποσό μπορεί να δώσει στον άλλο τα μισά. (Αφήστε τον τρίτο απ’ έξω για να το δείξετε. Δε χρειάζεται να τον ανακατέψετε.)

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 22 Οκτωβρίου, 2009 @ 10:59 πμ

  4. Μα πώς; Aς πούμε ο ένας έχει 17 και ο άλλος 4. Πώς μπορεί ο άρτιος να δώσει τα μισά στον περιττό αφού είναι μικρότερος; δεν επιτρεπεται από τους κανόνες.

    Μου αρέσει!

    Σχόλιο από pebox — 24 Οκτωβρίου, 2009 @ 10:09 πμ

  5. Μπορούμε να φανταστούμε τους αριθμούς σαν σημεία επάνω στον άξονα των φυσικών αριθμών τα οποία κινούνται. Έστω Α<=Β<=Γ. Αν είναι όλοι τους άρτιοι τότε μπορώ να παράγω κάθε άρτιο με τις δοσοληψίες που γίνονται ανάμεσα στον Α και τον Γ (οι δοσοληψίες με άρτιους πάντα σε άρτια ποσά με αφήνουν). Είναι σα να έχω ένα διάστημα και συστέλλω τα άκρα του (από αριστερά και από δεξιά) κατά το ίδιο ποσό, κι έχω κι ένα σημείο μέσα στο διάστημα που ορίζουν τα άκρα. Κάποτε κάποιο άκρο θα συμπέσει με το σημείο. Για περιττούς δεν έχω σκεφτεί, δεν διαιρούνται ακριβώς…

    Μου αρέσει!

    Σχόλιο από pebox — 24 Οκτωβρίου, 2009 @ 10:18 πμ

  6. Αυτά που λες για τους άρτιους δεν είναι σωστά αιτιολογημένα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 24 Οκτωβρίου, 2009 @ 1:56 μμ

  7. Υπόδειξη: Για να δείξετε αυτό που ζητάει η προηγούμενη υπόδειξη παρατηρείστε ότι αν δύο άτομα (θυμηθείτε ότι αγνοούμε τον τρίτο) έχουν άρτιο και περιττό ποσό τότε μετά από ένα γύρο (α) πάλι θα έχουμε ένα άρτιο και ένα περιττό και (β) κάθε τέτοια κατάσταση μπορεί να έχει προέλθει από μόνο μια άλλη.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 26 Οκτωβρίου, 2009 @ 12:50 μμ

  8. Έστω ένας από αυτούς περιττός και ένας άρτιος, τότε στις μεταξύ τους δοσοληψίες, κάποια στιγμή ο ένας από τους δύο θα φθάσει να έχει ποσό ίσο με τη μονάδα, ενώ ο άλλος θα έχει άρτιο ποσό. Σταματάνε εκέι τις δοσοληψίες.

    Εάν ο τρίτος είναι περιττός, τότε αυτός που έχει άρτιο ποσό ξεκινά μαζί του δοσοληψίες μέχρι κάποιος να έχει μονάδα. Μετά οι δύο φίλοι που έχουν μονάδες κάνουν μία τελευταία δοσοληψία μεταξύ τους.

    Εάν ο τρίτος είναι άρτιος τότε κάνει μία δοσοληψία με αυτόν που έχει μονάδα, οπότε ο τελευταίος αποκτά 2 μονάδες και ο άλλος περιττό. Οπότε αυτός με το περιττό ποσό κάνει δοσοληψία με τον άρτιο μέχρι κάποιος να αποκτήσει ποσό μονάδα. Στη συνέχεια κάνουν άλλη μία δοσοληψία μέχρι να αποκτήσει αυτός που έχει μονάδα, 2 μονάδες, και τελικά αυτοί που έχουν 2 μονάδες κάνουν μία τελευταία δοσοληψία.

    Μου αρέσει!

    Σχόλιο από pebox — 27 Οκτωβρίου, 2009 @ 11:07 μμ

  9. pebox, λες:

    Έστω ένας από αυτούς περιττός και ένας άρτιος, τότε στις μεταξύ τους δοσοληψίες, κάποια στιγμή ο ένας από τους δύο θα φθάσει να έχει ποσό ίσο με τη μονάδα, ενώ ο άλλος θα έχει άρτιο ποσό. Σταματάνε εκέι τις δοσοληψίες.

    Γιατί;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 27 Οκτωβρίου, 2009 @ 11:16 μμ

  10. ναι πιο σωστά ίσως θα ήταν να έλεγα σταματάνε εκεί τις δοσοληψίες και κοιτάνε τί ποσό έχει ο τρίτος, εάν έχει άρτιο ποσό μονάδων πέφτουν στη 2η περ. που έγραψα, εάν περιττό στην 1η.

    Μου αρέσει!

    Σχόλιο από pebox — 27 Οκτωβρίου, 2009 @ 11:30 μμ

  11. Γιατί θα φτάσουν να έχει κάποιος μονάδα;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 27 Οκτωβρίου, 2009 @ 11:32 μμ

  12. ναι σωστά δεν φτάνουν πάντα. δεν δουλεύει. νομιζω όμως ότι πάντα ανταλλάζουν χρήματα εάν επαναλλάβουν ικανές φορές τις δοσοληψίες

    Μου αρέσει!

    Σχόλιο από pebox — 27 Οκτωβρίου, 2009 @ 11:57 μμ

  13. Υποθέτουμε ότι ισχύει η υπόδειξη. Δηλαδή ότι αν ο ένας έχει x (ευρώ) και ο άλλος 2y με x περιττός τότε μετά από κάποιες δοσοληψίες θα έχουν x+y , y χωρίς να λαμβάνουμε υπόψη τη σειρά. Άρα αν έχουν x,2y με x περιττό τότε μετά από κάποιες δοσοληψίες θα έχουν x+y-\frac{y}{{2}^{a}} , \frac{y}{{2}^{a}} με \frac{y}{{2}^{a}} περιττό.
    Έχουμε τις περιπτώσεις:
    (Εκεί που δε θα γράφω ποιοι κάνουν τις δοσοληψίες θα προκύπτει από το αποτέλεσμα)
    1)Τα τρία άτομα έχουν x,y,2z με x,y περιττούς. Τότε μπορούμε να υποθέσουμε ότι x\le z, y\le z ( αν δεν ισχύει κάνουν δοσοληψίες οι x,2z μέχρι να ελαχιστοποιηθεί ο περιττός και μετά ο y με τον άρτιο μέχρι να ελαχιστοποιηθεί ο περιττός). Υποθέτουμε ακόμη ότι x\le yΑν x=y κάνουν μια τελευταία δοσοληψία. Αν x<y τότε μετά από μια δοσοληψία θα έχουν 2x,y,2z-x. Μετά από κάποιες δοσοληψίες θα έχουν x,y+x,2z-x (y+x άρτιος) και μετά από κάποιες δοσοληψίες θα έχουν x,\frac{x+y}{{2}^{a}},2z-x+y+x-\frac{x+y}{{2}^{a}} όπου ο \frac{x+y}{{2}^{a}} είναι περιττός. Επειδή \frac{x+y}{{2}^{a}}\le \frac{2y}{{2}^{a}}\le y με ισότητα αν x=y συνεχίζοντας με αυτό το τρόπο οι περιττοί θα ελαττώνονται συνεχώς μέχρι τα τρία άτομα να έχουν ποσά x',y',2z' με x'=y' (περιττός) οπότε κάνουν μία τελευταία δοσοληψία.
    2)Αν έχουν ποσά x,2y,2z με x περιττό μπορούμε να υποθέσουμε ότι x\le y , x\le z (αλλιώς κάνουν δοσοληψίες πρώτα οι x,2y και μετά ο περιττός με τον 2z σταματώντας σε κάθε περίπτωση όταν ελαχιστοποιηθεί ο περιττός). Μετά από μια δοσοληψία θα έχουν 2x,2y,2z-x, μετά από κάποιες δοσοληψίες θα έχουν 2x,\frac{y}{{2}^{a}},2z-x+2y-\frac{y}{{2}^{a}} με \frac{y}{{2}^{a}} περιττό και μετά από κάποιες δοσοληψίες θα έχουν x,\frac {y}{{2}^{a}}+x,2z-x+2y-\frac {y}{{2}^{a}}. Αφού \frac{y}{{2}^{a}}+x\le y+x\le 2y με ισότητα αν x=y συνεχίζοντας με αυτό το τρόπο κάποια στιγμή θα έχουν x',2y',2z' με x' περιττό και 2x'=2y' οπότε κάνουν μια δοσοληψία ο πρώτος με τον τρίτο και μετά ο πρώτος με τον δεύτερο.
    3)Αν έχουν και οι τρεις περιττό ποσό με μια δοσοληψία αναγόμαστε στη προηγούμενη περίπτωση.
    4)Αν τώρα έχουν x,y,z με x,y,z άρτιους τότε αν d είναι ο μ.κ.δ. των x,y,z και a φυσικός έτσι ώστε ο \frac {d}{{2}^{a}} είναι περιττός τότε η τριάδα \frac {x}{{2}^{a}},\frac {y}{{2}^{a}},\frac {z}{{2}^{a}} είναι σε κάποια από τις προηγούμενες περιπτώσεις. Ακολουθούμε τότε τον αλγόριθμο της περίπτωσης που ανήκει η \frac {x}{{2}^{a}},\frac {y}{{2}^{a}},\frac {z}{{2}^{a}} με την αντιστοιχία \frac {x}{{2}^{a}}\rightarrow x,\frac {y}{{2}^{a}}\rightarrow y,\frac {z}{{2}^{a}}\rightarrow z.
    Το τελευταίο ισχύει γιατί σε αυτή τη περίπτωση ο μ.κ.δ. των x,y είναι ίσος με τον μ.κ.δ. των 2x,y-x κ.ο.κ.
    Για να δούμε ότι ισχύει η υπόδειξη (αν x περιττός y άρτιος) μπορούμε να ορίσουμε το σύνολο A=\{ \{1,x+y-1\},\{2,x+y-2\},...,\{\frac {x+y-1}{2},\frac {x+y+1}{2}\} \} και την απεικόνιση \varphi : A\rightarrow A με \varphi(\{a,x+y-a\})=\{2a,x+y-2a\} για a=1,2,...,\frac {x+y-1}{2}. Τότε η φ είναι 1-1 και επί ( \varphi \in {S}_{\frac {x+y-1}{2}} ) και μετά από κάθε δοσοληψία το αποτέλεσμα είναι η εικόνα των ποσών που έχουν τα 2 άτομα μέσω της φ.

    Μου αρέσει!

    Σχόλιο από pamp0s — 20 Μαρτίου, 2010 @ 12:22 πμ

  14. pamp0s:

    Είμαι λίγο μπερδεμένος με τη λύση που προτείνεις. Για παράδειγμα, γράφεις στο τέλος της 1ης παραγράφου:
    x+y-\frac{y}{{2}^{a}} αλλά μάλλον εννοείς x+y+\frac{y}{{2}^{a}}.

    Επίσης μιλάς στο 1) για την ελαχιστοποίηση του περιττού αλλά δε βλέπω πώς.

    Αν μπορείς ξαναγράψε το πιο αναλυτικά. Οι πολλές περιπτώσεις κάνουν μια τέτοια απόδειξη κάπως δυσανάγνωστη. Αυτό μπορεί φυσικά να είναι αναπόφευκτο, αλλά αξίζει να βρίσκει κανείς ένα κομψό τρόπο να τη διατυπώσει.

    (Συγγνώμη για την καθυστερημένη απάντηση αλλά έλειπα κάποιες μέρες.)

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 22 Μαρτίου, 2010 @ 3:40 μμ

  15. Καλησπέρα.
    Έχετε δίκαιο στο ότι είναι δυσανάγνωστη η λύση αλλά δυστυχώς είναι ο καλύτερος τρόπος που μπορούσα να την παρουσιάσω. Θα εφαρμόσω όμως τον «αλγόριθμο» της περίπτωσης 1) σε συγκεκριμένο παράδειγμα και ελπίζω με αυτό να γίνω πιο κατανοητός.
    Πρώτα όμως στο τέλος της πρώτης παραγράφου το x+y-\frac {y}{{2}^{a}} νομίζω είναι σωστό. Σε κάθε δοσοληψία το άθροισμα των ποσών μετά την δοσοληψία είναι ίσο με το άθροισμα των ποσών πριν τη δοσοληψία. Αυτό που θέλω να πω εκεί είναι ότι αν ο ένας έχει περιττό ποσό και ο άλλος άρτιο και υποθέσουμε ότι αυτός που έχει το άρτιο ποσό μπορεί να δώσει στον άλλο τα μισά τότε μπορεί να το κάνει συνεχώς μέχρι να του μείνει περιττό ποσό. Για παράδειγμα αν ο ένας έχει 21 και ο άλλος 560 (=16\times35) μετά από κάποιες δοσοληψίες μπορεί ο δεύτερος να δώσει τα 280 (=8\times35) και να του μείνουν 280. Κάνοντας το ίδιο μπορεί μετά από κάποιες δοσοληψίες να μείνει με 35 οπότε ο πρώτος θα έχει (αναγκαστικά) 546 (=21+16\times35-35).

    Μου αρέσει!

    Σχόλιο από pamp0s — 23 Μαρτίου, 2010 @ 10:35 μμ

  16. Τώρα να εφαρμόσω την περίπτωση 1) σε συγκεκριμένο παράδειγμα.
    Έστω ότι έχουν τα ποσά 45,21,20. Εκεί που λέω για ελαχιστοποίηση του περιττού (» αν δεν ισχύει κάνουν δοσοληψίες οι x,2z μέχρι να ελαχιστοποιηθεί ο περιττός …») εννοώ να κάνουν το εξής:
    Αρχίζουν τις δοσοληψίες οι 45, 20 μέχρι να καταλήξουν με ποσά 45, 20 (αυτό γίνετε λόγο της τελευταίας παραγράφου του σχολίου 13). Σε κάθε δοσοληψία σημειώνουν το περιττό ποσό και βρίσκουν το ελάχιστο. Μετά ξαναρχίζουν τις δοσοληψίες μέχρι να πετύχουν αυτό το ελάχιστο περιττό ποσό. Στο παράδειγμα πρώτα κάνουν τις εξής δοσοληψίες \{45,20\}\rightarrow\{25,40\}\rightarrow\{50,15\}\rightarrow\{35,30\}\rightarrow\{5,60\}\rightarrow \{10,55\}\rightarrow \{20,45\}. Τα περιττά ποσά είναι 45,25,15,35,5,55,45 με ελάχιστο το 5. Οπότε ξαναρχίζουν τις δοσοληψίες και σταματούν όταν θα έχουν ποσά 5,60. Άρα τα ποσά των τριών έγιναν 5,21,60. Κάνουν το ίδιο οι 21,60 και μετά από δύο δοσοληψίες έχουν 3,78. Άρα τα ποσά των τριών γίνονται 5,3,78 και ισχύει 5\le\frac{78}{2},3\le\frac{78}{2} (Η ανισότητες θα ισχύουν στη γενική περίπτωση λόγο της πρώτης παραγράφου του σχόλιου 13).
    Μετά διατάσσουμε τα περιττά ποσά και έχουμε τα 3,5,78.
    Ακολουθώντας τον αλγόριθμο της περίπτωσης 1 κάνουμε τις εξής δοσοληψίες:
    \{3,5,78\}\rightarrow \{6,5,75\}\rightarrow \{3,8,75\}\rightarrow \{3,1,82\}.
    Τα διατάσσουμε σε {1,3,82} και συνεχίζουμε με τον ίδιο τρόπο.

    Μου αρέσει!

    Σχόλιο από pamp0s — 23 Μαρτίου, 2010 @ 11:14 μμ

  17. pamp0s:

    (Συγγνώμη για την καθυστερημένη απάντηση αλλά αυτές τις μέρες ταξιδεύω.)

    Νομίζω κατάλαβα τη λύση σου. Ας την ανακεφαλαιώσω λίγο για να ξεκαθαρίσω ορισμένα πράγματα. Αναφέρομαι λοιπόν στο σχόλιο 13.

    Στην αρχή του σχολίου η ποσότητα x+y-\frac{y}{2^a} πρέπει να γίνει x+2y-\frac{y}{2^a}.

    H απόδειξή σου για την υπόδειξη είναι σωστή μεν αλλά λείπει το εξής: για να πετύχουμε τη μετατροπή (x,2y) \to (x+y,y) (όπου x περιττό) κάνουμε συνεχώς την πράξη που επιτρέπεται να κάνουμε (δηλ. διπλασιάζουμε το μικρότερο ποσό σε βάρος του μεγάλου) και επειδή το σύνολο των δυνατών καταστάσεων είναι πεπερασμένο κάποια στιγμή θα «κλείσουμε κύκλο» και θα ξαναβρεθούμε στην αρχική μας κατάσταση (x,2y). Αν σταματήσουμε ένα βήμα πριν θα έχουμε αυτό που θέλουμε, δηλ. την κατάσταση (x+y,y).

    Οι περιπτώσεις σου 1 και 2 αντιστοιχούν σε περιττό και άρτιο συνολικό άθροισμα αντίστοιχα. Η περίπτωση 1 (άρτιο άθροισμα) μπορεί να μετετραπεί στην περίπτωση 4 (όλα άρτια) με μια μόνο πράξη (ανάμεσα στα δύο περιττά ποσά), οπότε δε χρειάζεται ξεχωριστή αντιμετώπιση.

    Κλειδί στη μέθοδό σου είναι αυτό που ονομάζεις «ελαχιστοποίηση του περιττού», δηλ. το ότι αν έχεις τα ποσά x, 2y με x περιττό, μπορείς να τα μετατρέψεις σε ένα ζεύγος περιττού-άρτιου ώστε να είναι ο περιττός το πολύ το μισό του αρτίου. Αυτό είναι που εξηγείς στην πρώτη παράγραφο του σχολίου 13.

    Η υπόλοιπη απόδειξη περιέχεται στην περίπτωση 2, που είναι μια χαρά.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 27 Μαρτίου, 2010 @ 1:47 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.