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

12 Απριλίου, 2010

Τραπουλόχαρτα σε σωρούς

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

Παίρνουμε μια συνηθισμένη τράπουλα (52 φύλλα σε 13 είδη, από 4 κάθε είδος), την ανακατεύουμε και την μοιράζουμε σε 13 σωρούς των 4 φύλλων.

Είναι πάντα δυνατό ή όχι να επιλέξουμε ένα φύλλο από κάθε σωρό ώστε στο τέλος να έχουμε ένα φύλλο από κάθε είδος;

11 Σχόλια »

  1. Υπόδειξη:

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

    Μπορείτε πάντα να το κάνετε αυτό; (Εννοείται πως σε διαφορετικά είδη πρέπει να αντιστοιχούν διαφορετικοί σωροί.)

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 21 Απριλίου, 2010 @ 5:34 μμ

  2. Υπόδειξη:

    «Πρέπει για καθένα από τα 13 είδη να επιλέξετε ακριβώς έναν από τους 13 σωρούς…»

    Παντρέψτε δηλ. τους σωρούς με τα είδη …

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 28 Απριλίου, 2010 @ 10:10 πμ

  3. Αν κατάλαβα σωστά το πρόβλημα, νομίζω ότι δεν είναι δυνατό να βρεθεί τρόπος επιλογής των φύλλων έτσι ώστε όπως και να γίνει το ανακάτεμα να επιλέγουμε πάντα 13 διαφορετικά είδη.
    Αν π.χ. δώσει κάποιος τη λύση:
    » Επιλέγουμε από τον i σωρό το a_i φύλλο (a_i\in\{1,2,3,4\},i=1,2,\ldots,13)»
    τότε μπορούμε να ανακατέψουμε τη τράπουλα με τέτοιο τρόπο έτσι ώστε τα φύλλα a_1 στον πρώτο σωρό και a_2 στον δεύτερο σωρό να είναι του ιδίου είδους.

    Μου αρέσει!

    Σχόλιο από pamp0s — 28 Απριλίου, 2010 @ 2:50 μμ

  4. Ο αλγόριθμος που προτείνεις είναι «τυφλός», δε λαμβάνει δηλ. υπόψιν του το πώς έχει κανείς ανακατέψει την τράπουλα και φτιάξει τους σωρούς. Όμως αυτό δεν είναι απαραίτητο. Τους σωρούς τους βλέπουμε πριν διαλέξουμε.

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 28 Απριλίου, 2010 @ 3:14 μμ

  5. Έστω ότι μετά από κάποιο ανακάτεμα διαλέξαμε από τους πρώτους k σωρούς k διαφορετικά είδη και ότι δεν μπορούμε να διαλέξουμε άλλο είδος από τους επόμενους σωρούς. Αριθμώντας κατάλληλα τα φύλλα μας (σε ίδια είδη δίνουμε τον ίδιο αριθμό) μπορούμε να υποθέσουμε ότι επιλέξαμε το i φύλλο από τον i σωρό για i=1,\ldots,k και ότι στους σωρούς k+1,\ldots,13 υπάρχουν μόνο φύλλα είδους 1,\ldots,k. Για να συμβαίνει αυτό πρέπει k\geq 8. Έστω ότι στον k+1 σωρό υπάρχει το φύλλο i_0 \;(i_0\le k). Αν στον i_0 σωρό υπάρχει φύλλο είδους j>k επιλέγουμε από τον i_0 σωρό το φύλλο j και από τον k+1 σωρό το φύλλο i_0. Αν δεν συμβαίνει το τελευταίο τότε στον i_0 σωρό υπάρχει φύλλο είδους i_1\neq i_0,\;i_1\le k. Αν στον i_1 σωρό υπάρχει φύλλο είδους j>k επιλέγουμε από τον i_1 σωρό το φύλλο j από τον i_0 σωρό το φύλλο i_1 και από τον k+1 σωρό το φύλλο i_0. Συνεχίζοντας με τον ίδιο τρόπο σίγουρα θα βρούμε φύλλο είδους j>k αφού ο μόνος τρόπος να μη συμβεί αυτό είναι να πέσουμε σε κύκλο. Δηλαδή να βρούμε αριθμούς i_0,\ldots,i_n\le k διαφορετικούς ανά δύο (άρα n\le k) έτσι ώστε στους σωρούς i_0,\ldots,i_n να υπάρχουν μόνο φύλλα είδους i_0,\ldots,i_n το οποίο δεν γίνετε αφού στον k+1 σωρό υπάρχει φύλλο είδους i_0.
    Άρα μπορούμε να διαλέξουμε από τους πρώτους k+1 σωρούς k+1 διαφορετικά είδη.

    Μου αρέσει!

    Σχόλιο από pamp0s — 13 Μαΐου, 2010 @ 11:07 μμ

  6. pamp0s:

    Η ιδέα σου είναι καλή και μάλλον μπορεί να σωθεί, αλλά όπως το γράφεις δε με πείθεις εκεί που λές

    …αφού ο μόνος τρόπος να μη συμβεί αυτό είναι να πέσουμε σε κύκλο. Δηλαδή να βρούμε αριθμούς i_0,\ldots,i_n\le k διαφορετικούς ανά δύο (άρα n\le k) έτσι ώστε στους σωρούς i_0,\ldots,i_n να υπάρχουν μόνο φύλλα είδους i_0,\ldots,i_n.

    Δηλ. το ότι μπορεί να κλείσεις κύκλο όπως πας δε μου φαίνεται να σημαίνει ότι οι σωροί που συμμετέχουν σε αυτόν τον κύκλο περιέχουν μόνο χαρτιά από τους σωρούς i_0,\ldots,i_n. Μπορεί απλά οι επιλογές που έκανες να ήταν εσφαλμένες.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 14 Μαΐου, 2010 @ 10:11 πμ

  7. Έχετε δίκαιο μπορεί οι επιλογές να ήταν εσφαλμένες. Συνεχίζω λοιπόν στο προηγούμενο σχόλιο μου.
    …Συνεχίζοντας με τον ίδιο τρόπο σίγουρα θα βρούμε φύλλο είδους j>k. Έστω προς άτοπο ότι σε κάθε επιλογή των i_r,\;r>0 δεν βρίσκουμε φύλλο είδους j>k στον σωρό i_r.
    Σε κάθε επιλογή των i_1,\ldots,i_n σίγουρα θα πέσουμε σε κύκλο ( εννοώντας i_n=i_r για κάποιο r\in\{0,\ldots,n-1\} και το n είναι το ελάχιστο με αυτή την ιδιότητα), αφού n\le k\;\;i_r\in\{1,\ldots,k\},\;r=1,\ldots,n. Από όλες τις δυνατές επιλογές των i_1,\ldots,i_n έστω j_1,\ldots,j_m όλα τα διαφορετικά ανά δύο i_r που εμφανίζονται. Τότε από τον τρόπο επιλογής των j_r στους σωρούς i_0,j_1,\ldots,j_m υπάρχουν μόνο φύλλα είδους i_0,j_1,\ldots,j_m το οποίο είναι αδύνατο.

    Μου αρέσει!

    Σχόλιο από pamp0s — 14 Μαΐου, 2010 @ 1:08 μμ

  8. Νομίζω πως τώρα είναι σωστό.

    Όμως υπάρχει και μια άλλη λύση που χρησιμοποιεί το λεγόμενο Θεώρημα του Γάμου (δείτε π.χ. εδώ για το θέωρημα αυτό), που είναι ένα πολύ εύχρηστο θεώρημα και καλό είναι να το έχει κανείς υπ’ όψιν του.

    Μπορείτε να τη βρείτε;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 15 Μαΐου, 2010 @ 12:49 πμ

  9. Έστω A_1,\ldots,A_{13} οι σωροί (σύνολα αριθμών που περιέχονται σε κάθε σωρό, τα χρώματα τα αγνοούμε). Τότε για κάθε J\subseteq \{1,\ldots,13\} οι σωροί που αντιστοιχούν στους δείκτες J έχουν 4|J| χαρτιά άρα τουλάχιστο |J| διαφορετικούς αριθμούς. Άρα |\bigcup_{j\in J}A_j| \geq |J| \forall J \subseteq \{1,\ldots,13\} το οποίο είναι η συνθήκη του Hall. Άρα από το θεώρημα του Γάμου υπάρχουν x_1\in A_1,\ldots,x_{13}\in A_{13} διαφορετικά ανά δύο το οποίο είναι το ζητούμενο.

    Μου αρέσει!

    Σχόλιο από pamp0s — 15 Μαΐου, 2010 @ 11:22 πμ

  10. Φυσικά αριθμήσαμε τα φύλλα τυχαία (σε ίδια είδη ίδιο αριθμό) και θεωρούμε τα A_i σαν σύνολα

    Μου αρέσει!

    Σχόλιο από pamp0s — 15 Μαΐου, 2010 @ 11:30 πμ

  11. Πολύ σωστά.

    Το θεώρημα του Hall είναι πάρα πολύ χρήσιμο και πρέπει κανείς να το έχει υπόψιν του μια και ξεπηδάει συχνά εκεί που δεν το περιμένεις.

    Ένα άλλο πρόβλημα που έχει τοποθετηθεί σε αυτό το blog αλλά δεν έχει λυθεί ακόμη, μπορεί επίσης να λυθεί με χρήση του θεωρήματος του Hall (συν λίγη εύκολη γεωμετρία). Αυτό είχε προκύψει παλιότερα στην έρευνά μου. Πρόκειται δηλ. για «ρεαλιστικό» πρόβλημα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 15 Μαΐου, 2010 @ 11:39 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Blog στο WordPress.com.