Σχετικά Πρώτοι

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

JimNt.
Δημοσιεύσεις: 507
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Σχετικά Πρώτοι

#1

Μη αναγνωσμένη δημοσίευση από JimNt. » Σάβ Ιουν 17, 2017 10:04 pm

Δίνεται το σύνολο A=\{1,2,..,1987\}. Να δείξετε ότι σε οποιοδήποτε υποσύνολο του A έστω B με |B|=1325 μπορούμε να βρούμε a,b,c τέτοια ώστε (a,b)=(b,c)=(c,a)=1. Ισχύει το ίδιο και για 1324; Για μαθητές.


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

Λέξεις Κλειδιά:
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 666
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Σχετικά Πρώτοι

#2

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Κυρ Ιουν 18, 2017 1:49 am

Χωρίζουμε τους αριθμούς στις εξής κατηγορίες:

- Οι αριθμοί που διαιρούνται με το 2
- Οι αριθμοί που διαιρούνται με το 3, αλλά όχι με το 2
- Οι αριθμοί που διαιρούνται με το 5, αλλά όχι με το 3 και το 2
.
.
.
- Οι αριθμοί που διαιρούνται με το 1987, αλλά με κανέναν από τους προηγούμενους πρώτους.

Με αυτό τον τρόπο είναι βέβαιο πως αριθμοί από διαφορετικές κατηγορίες είναι πρώτοι μεταξύ τους.

Έστω πως υπήρχε ένα υποσύνολο του A, έστω B', όπου δεν ίσχυε το ζητούμενο. Προφανώς θα έπρεπε οι αριθμοί που θα περιείχε να προέρχονταν από το πολύ δύο κατηγορίες, καθώς διαφορετικά θα επιλέγαμε 1 αριθμό από 3 διαφορετικές κατηγορίες και το ζητούμενο θα ίσχυε.

Θα αποδείξουμε πως δεν γίνεται να πάρουμε 1325 αριθμούς από μόνο 2 κατηγορίες:

Πράγματι ακόμα και αν πάρουμε από τις δύο μεγαλύτερες (σε πλήθος), δηλαδή τις δύο πρώτες, το συνολικό πλήθος είναι 993+331=1324, άρα ακόμα και σε αυτή την περίπτωση δεν καλύπτουμε 1325 αριθμούς, άτοπο.

Επομένως το ζητούμενο ισχύει όταν το πλήθος του B είναι 1325. Όταν είναι όμως 1324 δεν ισχύει, όπως δείξαμε στο παραπάνω (παίρνοντας τους αριθμούς της πρώτης και της δεύτερης κατηγορίας.)

Υ.Γ Η λύση είναι τελείως λάθος :oops: . Αναμενόμενο βέβαια, όταν πας να λύσεις μια άσκηση μετά τα μεσάνυχτα :roll: .
τελευταία επεξεργασία από Διονύσιος Αδαμόπουλος σε Κυρ Ιουν 18, 2017 5:10 pm, έχει επεξεργασθεί 2 φορές συνολικά.


Houston, we have a problem!
JimNt.
Δημοσιεύσεις: 507
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Σχετικά Πρώτοι

#3

Μη αναγνωσμένη δημοσίευση από JimNt. » Κυρ Ιουν 18, 2017 11:22 am

Διονύσιος Αδαμόπουλος έγραψε:Χωρίζουμε τους αριθμούς στις εξής κατηγορίες:

- Οι αριθμοί που διαιρούνται με το 2
- Οι αριθμοί που διαιρούνται με το 3, αλλά όχι με το 2
- Οι αριθμοί που διαιρούνται με το 5, αλλά όχι με το 3 και το 2
.
.
.
- Οι αριθμοί που διαιρούνται με το 1987, αλλά με κανέναν από τους προηγούμενους πρώτους.

Με αυτό τον τρόπο είναι βέβαιο πως αριθμοί από διαφορετικές κατηγορίες είναι πρώτοι μεταξύ τους.

Έστω πως υπήρχε ένα υποσύνολο του A, έστω B', όπου δεν ίσχυε το ζητούμενο. Προφανώς θα έπρεπε οι αριθμοί που θα περιείχε να προέρχονταν από το πολύ δύο κατηγορίες, καθώς διαφορετικά θα επιλέγαμε 1 αριθμό από 3 διαφορετικές κατηγορίες και το ζητούμενο θα ίσχυε.

Θα αποδείξουμε πως δεν γίνεται να πάρουμε 1325 αριθμούς από μόνο 2 κατηγορίες:

Πράγματι ακόμα και αν πάρουμε από τις δύο μεγαλύτερες (σε πλήθος), δηλαδή τις δύο πρώτες, το συνολικό πλήθος είναι 993+331=1324, άρα ακόμα και σε αυτή την περίπτωση δεν καλύπτουμε 1325 αριθμούς, άτοπο.

Επομένως το ζητούμενο ισχύει όταν το πλήθος του B είναι 1325. Όταν είναι όμως 1324 δεν ισχύει, όπως δείξαμε στο παραπάνω (παίρνοντας τους αριθμούς της πρώτης και της δεύτερης κατηγορίας.)
Δεν ισχύει αυτό οι 6, 3 π.χ δεν είναι πρώτοι μεταξύ τους.


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.
socrates
Επιμελητής
Δημοσιεύσεις: 5761
Εγγραφή: Δευ Μαρ 09, 2009 1:47 pm
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

Re: Σχετικά Πρώτοι

#4

Μη αναγνωσμένη δημοσίευση από socrates » Κυρ Ιουν 18, 2017 3:45 pm

Γράφουμε τους αριθμούς 1,2,..,1987 ως εξής:

1,2,3
4,5,6
...
1984,1985,1986
1987

Αν υπάρχουν και οι τρεις από μια γραμμή, τότε είναι ανά δύο πρώτοι μεταξύ τους.
Αλλιώς, έχουμε ακριβώς δύο από κάθε γραμμή και τον 1987.
Οπότε σίγουρα θα υπάρχει κάποια από τις τριάδες
\{1987,1986,1985\}
\{1987,1986, 1\}
\{1987,1984, 3\}
\{1987,1985,1984\}


Θανάσης Κοντογεώργης
Απάντηση

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

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

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