Τρίτη 1 Σεπτεμβρίου 2015

Χρωματισμός

Βάφουμε τους αριθμούς $1, 2, 3, ..., 20$ με δύο χρώματα άσπρο και μαύρο έτσι, ώστε να χρησιμοποιούνται και τα δύο χρώματα. Με πόσους τρόπους μπορεί να γίνει ο χρωματισμός ώστε το γινόμενο των άσπρων αριθμών και το γινόμενο των μαύρων αριθμών να έχουν μέγιστο κοινό διαιρέτη ίσο με $1$;
31η Ελληνική Μαθηματική Ολυμπιάδα "Ο Αρχιμήδης" 
22 Φεβρουαρίου 2014 Θέματα μικρών τάξεων
 Διασκεδαστικά Μαθηματικά    www.eisatopon.blogspot.com     
Αναρτήθηκε από στις 1.9.15
Ετικέτες

5 σχόλια:

  1. ΕΥΘΥΜΗΣ ΑΛΕΞΙΟΥ1 Σεπτεμβρίου 2015 στις 10:22 μ.μ.

    Το $1$ μπορεί να βαφεί με δύο τρόπους ( άσπρο ή μαύρο). Το $2$ μπορεί να βαφεί με δύο τρόπους ( άσπρο ή μαύρο).
    Όλοι οι άρτιοι πρέπει να πάρουν το χρώμα του $2$, δηλαδή οι αριθμοί $2,4,6,8,10,12,14,16,18,20$ και κατά συνέπεια και όλοι οι αριθμοί που έχουν κοινό διαιρέτη με αυτούς παίρνουν το χρώμα του $2$, δηλαδή οι αριθμοί $3,5,7,9,15$. Απέμειναν οι πρώτοι αριθμοί $11,13,17,19$ που μπορούν να βαφούν με $2$ τρόπους ( άσπρο ή μαύρο).
    Επομένως, συνολικά ο χρωματισμός μπορεί να γίνει με $2^6=64$ τρόπους.
    Επειδή όμως στο $64$ είναι και οι δύο περιπτώσεις όλοι οι αριθμοί μαύροι ή όλοι οι αριθμοί άσπροι και επειδή πρέπει να χρησιμοποιηθούν και τα δύο χρώματα, τις αφαιρούμε.
    Συνεπώς έχουμε συνολικά $64-2=62$ τρόπους χρωματισμού.

    ΑπάντησηΔιαγραφή
  2. papadim2 Σεπτεμβρίου 2015 στις 9:48 π.μ.

    Ωραίο πρόβλημα και συμφωνώ απολύτως με την ωραία ανάλυση του Ευθύμη!
    Θα διερωτηθώ μόνο ποια είναι η απάντηση στην περίπτωση που οι αριθμοί έφταναν μέχρι το 30 ή το 40.

    ΑπάντησηΔιαγραφή
  3. ΕΥΘΥΜΗΣ ΑΛΕΞΙΟΥ2 Σεπτεμβρίου 2015 στις 6:18 μ.μ.

    Με αφορμή τον προβληματισμό [:-) ] του Θανάση και προσπαθώντας να το γενικεύσω όσο γίνεται και όσο μπορώ περισσότερο κατέληξα, με επιφύλαξη βέβαια, στα παρακάτω
    Για τους αριθμούς $1,2,3,...,50$
    $1,2$ με δύο τρόπους $\Rightarrow 2^2$ τρόποι.
    $4,6,8,10,12,$ $14,16,18,20,$ $22,24,26,$ $28,30,32,$ $34,36,38,40,42,$ $44,46,48,50$ και
    $3,5,7,$ $9,11,$ $13,15, $$17,19,$$21,25,27,33$ $,35,39,45,49$ με ένα τρόπο, το χρώμα του $2$
    $29,31,37,41,43,47 $ με δύο τρόπους $\Rightarrow 2^6$ τρόποι.
    Άρα συνολικά $2^2\cdot 2^6-2=2^8-2=254$ τρόποι.

    Και γενικά αν $N$ o μεγαλύτερος γνωστός πρώτος αριθμός και $m$ το πλήθος των πρώτων αριθμών που είναι $>\dfrac{N+1}{2}$ τότε ο χρωματισμός των αριθμών $1,2,3,...,N+1$ μπορεί να γίνει με $2^{2+m}-2$

    ΑπάντησηΔιαγραφή
  4. papadim2 Σεπτεμβρίου 2015 στις 6:23 μ.μ.

    Πολύ ωραία, κατά την άποψή μου, η κάλυψη από τον Ευθύμη και της περίπτωσης 1-50 (ας προσθέσουμε Ευθύμη και τον 23 στους ομόχρωμους του 2), αν και άφησε να συναγάγω μόνος μου :-) τους τρόπους χρωματισμού στις περιπτώσεις 1-30, 1-40. Νομίζω ότι και στις δύο περιπτώσεις έχουμε 62 τρόπους, όσους δηλαδή και στην 1-20.
    Ωραία και η γενίκευσή σου Ευθύμη, επίτρεψέ μου να σε συγχαρώ και πάλι!
    Νομίζω ότι θα συμφωνήσουμε τελικά στο ότι ελευθερία επιλογής χρώματος έχουν το 1, ενιαία η ομάδα των σύνθετων του διαστήματος μαζί με τους πρώτους διαιρέτες τους, που συμβαίνει να βρίσκονται στο πρώτο μισό του διαστήματος 1-ν (η ομάδα των ομόχρωμων του 2) και κάθε πρώτος του δεύτερου μισού του διαστήματος 1-ν.

    ΑπάντησηΔιαγραφή
  5. ΕΥΘΥΜΗΣ ΑΛΕΞΙΟΥ2 Σεπτεμβρίου 2015 στις 8:18 μ.μ.

    Γεια σου Θανάση και σε ευχαριστώ
    Φυσικά συμφωνούμε - γιατί όμως "τελικά", διαφωνήσαμε μήπως "αρχικά" και δεν το κατάλαβα;
    Φαίνεται εξάλλου στην γενίκευση που έκανα, άσχετα αν συνειδητά δεν το έγραψα αφήνοντας το σε εσένα όπως και τις περιπτώσεις $1-30$ και $1-40$ :-) και πράγματι είναι $62$, αφού και στις τρεις περιπτώσεις οι πρώτοι που βρίσκονται στο $2$ο μισό της κάθε ακολουθίας είναι $4$...
    Απολογούμαι για το $23$ που πληκτρολογικά, μου διέφυγε...

    ΑπάντησηΔιαγραφή

Εγγραφή σε: Σχόλια ανάρτησης (Atom)