Σάββατο 20 Σεπτεμβρίου 2014

Ακέραιη Παλάντζα

Μια παλάντζα ισορροπεί με κάποια ζύγια και στα δύο σκέλη της. Κάθε ζύγι έχει μάζα ακέραιο αριθμό γραμμαρίων. Σε κάθε σκέλος της παλάντζας κανένα ζύγι δεν έχει το ίδιο βάρος με άλλο. Ο ζυγός ισορροπεί έχοντας $Β$ γραμμάρια σε κάθε σκέλος του.
Το $Β$ είναι μικρότερο από το γινόμενο των δύο αριθμών των βαριδιών στο αριστερό και στο δεξί σκέλος. Αληθεύει πάντα πως μπορούμε να αφαιρέσουμε κάποιο ή κάποια ζύγια/βαρίδια, αλλά όχι όλα, το ίδιο κι από τις δύο πλευρές της παλάντζας, κι αυτή να συνεχίσει να ισορροπεί;

7 σχόλια:

  1. YΠΟΔΕΙΞΗ: Tα δεδομένα επαρκούν για να γίνει διερεύνση κάποιων τιμών. Μπορεί κάποιος από την ανισότητα $B<x*y$ αν έστω x και y oι αριθμοί απ'τα βαρίδια ένθεν κι ένθεν ,αντίστοιχα, να βρει αν τα x και y μπορεί να είναι 1 , ή μεγαλύτερα...
    Μετά ,μπορεί να γίνει μια εις άτοπον απαγωγή.
    Μπορεί να καταστρωθεί, με βάση την υπόθεση πως δεν υπάρχει το ίδιο ακέραιο βάρος δεξιά και αριστερά αντίστοιχα και με βάση το ότι όλες οι μάζες είναι ακέραιες ,μια σχέση που να συνδέει τα x και y με κάποιο όριο, και να καταστρωθεί μια ανισότητα. Αν αυτή καταλήξει σε άτοπο, το πρόβλημα έχει λυθεί.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. "Αν αυτή καταλήξει σε άτοπο, το πρόβλημα έχει λυθεί." δηλαδή έχει απαντηθεί θετικά.

      Διαγραφή
    2. Υστερα από τις υποδείξεις του Γιώργου, παραθέτω κάποιους συλλογισμούς:

      Για να αποδείξουμε το ζητούμενο, αρκει να δείξουμε ότι υπάρχει τουλάχιστον ένα βάρος ίσης αξίας σε κάθε ζυγό. Προς τούτο θα χρησιμοποιήσουμε άτοπο απαγωγή, δηλαδή θα θεωρήσουμε κατ’αρχήν ότι δεν υπάρχουν κοινά βάρη στους δύο ζυγούς, με άλλα λόγια ότι όλα τα βάρη και στους δύο ζυγούς είναι διαφορετικά.
      Εστω ν ο αριθμός των βαρών στον ένα ζυγό και μ ο αριθμός των βαρών στον άλλον, με ν<=μ. Εχουμε ότι Β=1, Χ2>=2…….. Χν>=ν, Χν+11>=ν+1,Χν+2>=ν+2,…..Χν+μ>=ν+μ, επομένως:
      Χ1+Χ2+…+Χν+Χν+1+Χν+2+….+Χν+μ>=1+2+…..+ν+ν+1+……..+ν+μ
      Το πρώτο μέλος της ανωτέρω σχέσης ισούται με το βάρος και των δύο ζυγών, δηλαδή με 2*Β, ενώ το δεύτερο μέλος ισούται με το άθροισμα των πρώτων ν+μ φυσικών αριθμών, δηλαδή (ν+μ)*(ν+μ+1)/2. Αρα:
      2*Β>=(ν+μ)*(ν+μ+1)/2. Και επειδή Β(ν+μ)*(ν+μ+1), δηλαδή
      2*μ*ν>μ^2+μ+ν+ν^2, ή ισοδύναμα,
      0>(μ-ν)*(μ-ν+1), πράγμα άτοπο καθ’όσον εξ’υποθέσεως μ>=ν

      Διαγραφή
    3. Για κάποιο λόγο ένα τμήμα της απόδειξης κοβεται...
      Το μεσαίο τμήμα που εχει κοπεί, είναι:
      Εστω ν ο αριθμός των βαρών στον ένα ζυγό και μ ο αριθμός των βαρών στον άλλον, με ν<=μ. Εχουμε ότιι Β=1, Χ2>=2,......

      Διαγραφή
  2. Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.

    ΑπάντησηΔιαγραφή
  3. Έστω α1, α2, .., αν τα ν στον αριθμό ζύγια της μιας μεριάς και β1, β2, .., βμ τα μ στον αριθμό ζύγια της άλλης μεριάς.
    Από τα δεδομένα του προβλήματος έχουμε:
    Β = α1+α2+..+αν ≥ 1+2+..+ν = ν(ν+1)/2 και
    Β = β1+β2+..+βμ ≥ 1+2+..+μ = μ(μ+1)/2
    Επίσης Β < μ*ν
    Για να είναι πάντα δυνατή η διατήρηση της ισορροπίας της ζυγαριάς, μετά από την αφαίρεση ισάριθμων ζυγιών από τη μια και την άλλη πλευρά, θα αρκούσε να υπάρχει ένα τουλάχιστον ζύγι ίδιου βάρους και στις δυο πλευρές. Ας υποθέσουμε λοιπόν ότι δεν υπάρχει τέτοιο ζύγι, ότι δηλαδή τα α1, α2, .., αν, β1, β2, …, βμ έχουν όλα διακριτά βάρη μεταξύ τους. Σε τέτοια περίπτωση θα είχαμε:
    2B = α1+α2+..+αν+ β1+β2+..+βμ ≥ 1+2+..+(ν+μ) = (ν+μ)*(ν+μ+1)/2 και ταυτόχρονα 2Β < 2μ*ν. Θα ίσχυε επομένως:
    (ν+μ)*(ν+μ+1)/2 < 2μ*ν ==> (ν+μ)*(ν+μ+1) < 4μ*ν ==>
    ν^2+μ^2+2μ*ν +μ +ν < 4μ*ν ==> ν^2+μ^2-2μ*ν+μ+ν <0 ==> (ν-μ)^2+μ+ν <0, άτοπο διότι τα μ,ν είναι θετικοί ακέραιοι, ενώ το τετράγωνο της διαφοράς τους είναι μη αρνητικός ακέραιος.
    Επομένως, για να ικανοποιούνται οι αρχικές συνθήκες ισορροπίας, πάντα υπάρχει ένα τουλάχιστον ζύγι ίδιου βάρους και στις δυο πλευρές και άρα είναι πάντα δυνατή η διατήρηση της ισορροπίας της ζυγαριάς, μετά από την αφαίρεση ισάριθμων ζυγιών από τη μια και την άλλη πλευρά.

    ΑπάντησηΔιαγραφή
  4. Πολύ σωστά Στράτο και Θανάση! Συγχαρητήρια και στους δυο σας. Λύσατε με ωραία ανάλυση ένα δύσκολο πρόβλημα!

    Να προσθέσω απλώς ,την εντελώς "τυπικούρα/σχολαστικίλα" της υπόθεσης, πως το ότι δεν μπορεί να υπάρχει $1$ μόνο βαράκι ένθεν κι ένθεν, εξασφαλίζεται από το $B<μ*ν$ εφόσον δεν γίνεται να ισχύει B<μ (ή ν αντίστοιχα) .

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