Αθροίσματα ανά δύο σύνθετοι αριθμοί: Γενίκευση

[abfx]

Με αφορμή το θέμα εδώ ας δούμε το γενικότερο:

Ποιο είναι το ελάχιστο δυνατό πλήθος στοιχείων που μπορούμε να σβήσουμε από το σύνολο , ώστε το άθροισμα οποιωνδήποτε δύο να είναι σύνθετος αριθμός;

[Mihalis_Lambrou]

Ενδιαφέρον.

Έχω λύση με Θεώρημα Bertrand (βλέπε εδώ). Αυτό έχεις κατά νου, ή έχεις στοιχειώδη λύση;

Το ρωτάω, λόγω φακέλου.

[abfx]

Ενδιαφέρον.

Έχω λύση με Θεώρημα Bertrand (βλέπε εδώ). Αυτό έχεις κατά νου, ή έχεις στοιχειώδη λύση;

Το ρωτάω, λόγω φακέλου.

Κύριε Λάμπρου,

Η λύση που έχω κατά νου όντως χρησιμοποιεί το εν λόγω θεώρημα. Στοιχειώδη λύση δεν έχω. Θεώρησα ότι ο φάκελος είναι κατάλληλος, μιας και για το Θεώρημα Bertrand γίνεται μνεία και στο διαγωνιστικό βιβλίο Number Theory: Concepts and Problems των Andreescu, Dospinescu, Mushkarov σελ 380. Αν παρόλα αυτά έκρινα λάθος, ας μεταφερθεί το θέμα σε πιο "βαρύ" φάκελο.

Ευχαριστώ.

[ksofsa]

Μια λύση με ισχυρή επαγωγή και Bertrand.

Έστω ότι για κάθε αριθμό μικρότερο είτε ίσο με , το μέγιστο σύνολο με την εν λόγω ιδιότητα περιέχει τα μισά στοιχεία.

Θα δείξω για .

Από Bertrand, υπάρχει πρώτος μεταξύ και .

Έστω .

Διαμερίζω το αρχικό σύνολο σε δύο υποσύνολα .

Το μέγιστο σύνολο του πρώτου συνόλου περιέχει στοιχεία.

Για το δεύτερο υποσύνολο, το διαμερίζουμε σε ζεύγη, το πρώτο με το τελευταίο, το δεύτερο με το προτελευταίο κλπ.

Στο μέγιστο σύνολο του δεύτερου αυτού συνόλου θα υπάρχει το πολύ 1 στοιχείο από κάθε ζεύγος.

Δηλαδή το μέγιστο σύνολο έχει στοιχεία (π.χ. τους άρτιους).

Το τελικό μέγιστο υποσύνολο έχει στοιχεία, π.χ. όλους τους άρτιους ή όλους τους περιττούς.

[Mihalis_Lambrou]

Με αφορμή το θέμα εδώ ας δούμε το γενικότερο:

Ποιο είναι το ελάχιστο δυνατό πλήθος στοιχείων που μπορούμε να σβήσουμε από το σύνολο , ώστε το άθροισμα οποιωνδήποτε δύο να είναι σύνθετος αριθμός;

Θα δείξουμε (ισχυροποιώντας το ζητούμενο) ότι τα μόνα μέγιστα υποσύνολα του που μπορούν να παραμείνουν είναι α) οι άρτιοι και β) περιττοί του. Και στις δύο περιπτώσεις, μένει το μισό σύνολο.

Με επαγωγή και Bertrand: Για μικρά , απλό. Για το επαγωγικό βήμα, εξετάζουμε το . Επειδή οι άρτιοι (ή οι περιττοί) είναι παράδειγμα συνόλου με τις ζητούμενες ιδιότητες, σημαίνει ότι το μέγιστο πλήθος στοιχείων του ζητούμενου υποσυνόλου είναι στοιχεία. Θα δείξουμε ότι έχει ακριβώς στοιχεία δείχνοντας ότι δεν μπορεί να είναι .

Έστω, λοιπόν, ότι περιέχει στοιχεία.

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

Πράγματι, παρατηρούμε ότι η υπόθεση απαιτεί να μην είναι πρώτος κανένας από τους

και και ... . Όμως από Θεώρημα Bertrand μεταξύ του και του υπάρχει (περιττός) πρώτος (οι άρτιοι σίγουρα δεν είναι αυτός ο πρώτος). Αλλά αυτό συγκρούεται με την κατασκευή του υποσυνόλου.

Τελικά ο δεν βρίσκεται στο υποσύνολο. Άρα το ίδιο αποτελείται μόνο από περιττούς, όπως θέλαμε.

Όμοια η περίπτωση που το μέγιστο υποσύνολο του ήταν οι άρτιοι. Τελειώσαμε.

[Demetres]

Ενδιαφέρον.

Έχω λύση με Θεώρημα Bertrand (βλέπε εδώ). Αυτό έχεις κατά νου, ή έχεις στοιχειώδη λύση;

Το ρωτάω, λόγω φακέλου.

Δεν «μπορούμε» να έχουμε λύση χωρίς Bertrand. Αν πάρουμε το υποσύνολο με στοιχεία, για να δείξουμε ότι δεν μας κάνει, πρέπει να δείξουμε ότι τουλάχιστον ένας από τους είναι πρώτος. Που είναι ουσιαστικά το Bertrand.