Πέμπτη, 20 Νοεμβρίου 2014

Ελάχιστη τιμή

Δίνεται ένα σύνολο 1998 διαφορετικών φυσικών αριθμών. Κανείς από αυτούς δεν είναι δυνατόν να γραφεί ως άθροισμα δύο άλλων αριθμών του συνόλου. Ποια είναι η ελάχιστη δυνατή τιμή του μεγαλύτερου αριθμού του συγκεκριμένου συνόλου;
(Quantum - V.Y. Protasov)

9 σχόλια:

  1. Ενα πιθανό σύνολο είναι οι πρώτοι 1998 περιττοί αριθμοί (1,3,5,7....). Κανένας περιττός δεν μπορεί να γραφεί σαν άθροισμα δύο άλλων περιττών. Οπότε ο ζητούμενος αριθμός είναι ο 1998*2-1=3995

    ΑπάντησηΔιαγραφή
  2. Το σύνολο $(1,3,5,7,...,3995)$ είναι σύνολο $1998$ διαδοχικών περιττών αριθμών, όπου κανένας δεν μπορεί να εκφρασθεί ως άθροισμα δύο άλλων αριθμών του συνόλου καθώς περιττός +περιττός = άρτιος αριθμός

    ΑπάντησηΔιαγραφή
  3. Το σύνολο {1997, 1998, 1999, …. , 3994} έχει 1998 διαδοχικούς φυσικούς και επίσης κανένας τους δεν προκύπτει ως άθροισμα δύο άλλων. Μέγιστος ο 3994.

    ΑπάντησηΔιαγραφή
  4. Ευχαριστώ Στράτο. Παραθέτω και ένα σκεπτικό, για την περίπτωση διαδοχικών φυσικών:
    Αν ο ελάχιστος φυσικός του συνόλου είναι ο ν, τότε, για να μην προκύπτει κανένας αριθμός ως άθροισμα δύο άλλων, πρέπει (και αρκεί) το ελάχιστο άθροισμα δύο μελών του συνόλου να είναι μεγαλύτερο του μέγιστου φυσικού του συνόλου.
    Δηλαδή πρέπει:
    ν+(ν+1) > ν+1997 ==> ν > 1996 ==> ν=1997 ο ελάχιστος και ν+1997=3994 ο μέγιστος φυσικός του συνόλου.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Συμφωνώ με την ανάλυση που παραθέτεις Θανάση, και σαφώς η λύση που προτείνεις είναι η βέλτιστη για τη περίπτωση όπου οι αριθμοί είναι διαδοχικοί.
      Παρ'ότι πιστεύω ότι αυτή είναι η σωστή λύση, αναρωτιέμαι αν θα μπορούσε να αποδειχθεί θεωρητικά ότι δεν υπάρχει άλλη λύση (δηλαδή λύση με μη διαδοχικούς αριθμούς), που να καταλήγει σε μικρότερο μέγιστο αριθμό.

      Διαγραφή
  5. Στράτο, πάν σ'αυτό αν θεωρήσουμε πως μπορεί να υπάρξει μικρότερος μέγιστος από το 3994 και έστω v < ή ίσος με 3993 αυτός ο αριθμός ,αν χωρίσεις το σύνολο σε ζεύγη (1, ν-1), (2-ν-2),...κ.λ.π. άθροισμα σε καθε παρένθεση =ν.
    Υπάρχουν 1997 τέτοια ζευγαράκια. Όμως το σύνολό μας περιέχει ακριβώς 1997 διαφορετικού αριθμούς μικρότερους του ν.
    Από Περιστερώνα λοιπόν τουλάχιστον 2 ανήκουν στο ίδιο ζεύγος και έχουν άθροισμα ν. Άτοπο.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Ήμουνα ίσως λίγο υπέρ το δέον βιαστικός και ενδεχομένως ασαφής.
      Εννοούσα πως υπάρχουν ΤΟ ΠΟΛΥ ν/2 <3994/2=1997 τέτοια ζεύγη.Όμως το σύνολό μας περιέχει ακριβώς 1997 διαφορετικού αριθμούς ... (τα υπόλοιπα ως έχουν αποπάνω. :-) )

      Διαγραφή
  6. Πολύ ωραίο το επιχείρημα του περιστερώνα και μπράβο Γιώργη!
    Μια διαφορετική διατύπωση της απόδειξης, που νομίζω ότι αποδίδει την ίδια ουσία θα μπορούσε να είναι η εξής:
    Αν αφαιρούσαμε από το σύνολο {1997, 1998, 1999, … , 3994} μόνο τον μέγιστο 3994, τότε μέγιστος θα γινόταν ο 3993 και, για να παραμείνει 1998 ο πληθάριθμος του συνόλου, θα έπρεπε να προστεθεί στο σύνολο, ένας ακόμα φυσικός, από το εύρος 1 έως 1996 (1996 επιλογές). Αφού όμως στο αρχικό σύνολο θα παρέμεναν όλοι οι φυσικοί από 1997 έως 3993, τότε ο νεοεισερχόμενος αριθμός προστιθέμενος με κάποιον από τους προϋπάρχοντες θα έδινε οπωσδήποτε άθροισμα 3993, αφού:
    1+3992 = 2+3991 = 3+3990 =….= 1996+1997 = 3993
    Αν αφαιρούσαμε από το αρχικό σύνολο και τον 3993, τότε θα έπρεπε να προστεθεί άλλος ένας (1995 επιλογές), αλλά πλέον θα είχαμε ανάλογο πρόβλημα με τον 3992 και μετά με τον 3991, τον 3990 κ.ο.κ.
    Για να μην υπάρχει τελικά πρόβλημα, θα έπρεπε από το αρχικό σύνολο να αφαιρεθούν και οι 1998 αρχικοί φυσικοί, αλλά ακόμα και χωρίς έλεγχο αθροισμάτων των αντικαταστατών τους, οι επιλογές αντικατάστασης είναι μόνο 1996. Αδύνατο.

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