Σάββατο 22 Νοεμβρίου 2014

Διοφαντικές λύσεις

Ένα πρόβλημα του φίλου Θανάση Παπαδημητρίου.
Πόσες θετικές ακέραιες λύσεις έχει η εξίσωση:
$x+y+z=201$
για $x<y<z$;
Αναρτήθηκε από στις 22.11.14
Ετικέτες ,

9 σχόλια:

  1. pantsik22 Νοεμβρίου 2014 στις 11:57 π.μ.

    Βρήκα μια brute force λύση που μου φαίνεται σωστή. Για x=1 υπάρχουν 98 λύσεις. Για x=2 υπάρχουν 97 λύσεις. Για x=3 υπάρχουν 95 λύσεις. Για x=4 υπάρχουν 94 λύσεις, κλπ. Δηλαδή τα πλήθη των λύσεων γίνονται ζευγάρια με ένα ενδιάμεσο πλήθος να λείπει. Τα δύο τελευταία πλήθη είναι τα 2 και 1. Το άθροισμα όλων αυτών είναι 3267.

    ΑπάντησηΔιαγραφή
  2. stratos22 Νοεμβρίου 2014 στις 11:59 π.μ.

    Το x μπορεί να πάρει τιμές από 1-66, το y από 2-99, και το z από 3-198
    Για x=1, υπάρχουν 98 δυνατές τιμές του y (2-99)
    Για x=2, υπάρχουν 97 δυνατές τιμές του y (3-99)
    Για x=3, υπάρχουν 95 δυνατές τιμές του y (4-98)
    Παρατηρούμε ότι για κάθε αύξηση στη τιμή του x, έχουμε κατ'αρχήν μία κατά ένα μείωση στον αριθμό τιμών του y (καθ'όσον το y δεν πρέπει να είναι μεγαλύτερο του X), ενώ εάν το x είναι περιττός, έχουμε μία επιπλέον μείωση κατά ένα στον αριθμό τιμών του y λόγω της απαίτησης το z να είναι μεγαλύτερο του y.
    Ετσι μαθηματικοποιώντας τα ανωτέρω έχουμε ότι:
    Αν x περιττός (1-65), τότε αριθμός τιμών του y: Τy=(199-3*x)/2, και θέτοντας x=2*k-1, Ty=101-3*k (k=1-33)
    Αν x άρτιος (1-66), τότε αριθμός τιμών του y: Τy=(200-3*x)/2, και θέτοντας x=2*k, Ty=100-3*k (k=1-33)
    Αρα συνολικός αριθμός λύσεων:
    Σ(101-3κ)+Σ(100-3κ), κ=1-33, που ισούται με 3333+3300-6*33*34/2=3.267

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. pantsik22 Νοεμβρίου 2014 στις 1:42 μ.μ.

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

      Διαγραφή
  3. swt22 Νοεμβρίου 2014 στις 12:46 μ.μ.

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

    ΑπάντησηΔιαγραφή
  4. RIZOPOULOS GEORGIOS22 Νοεμβρίου 2014 στις 8:20 μ.μ.

    Σωστά αγαπητοί Πάνο και Στράτο!
    Πάνο,με μπρουτ φορς το αντιμετώπισα κι εγώ ,μόνο που το πήγα κάπως ανάποδα υπολογίζοντας τελικά το 1+2+4+5+7+8+... (66 όροι)
    Στράτο ,πολύ ωραία η ανάλυσή σου και θαυμαστό το σπάσιμο και ο υπολογισμός των δύο υποσειρών!
    Ωραία είναι και η συνδυστική προσέγγιση του Θανάση, αλλά ας μην τον υποκαταστήσω.

    ΑπάντησηΔιαγραφή
  5. papadim22 Νοεμβρίου 2014 στις 10:49 μ.μ.

    Ευχαριστώ και συγχαίρω τους φίλους Πάνο, Στράτο και Γιώργο για τις εξαιρετικές λύσεις, αναλύσεις και σχόλια. Γιώργη, εκτιμώ ιδιαιτέρως την καλή φιλοξενία που πάντα πρόθυμα προσφέρεις στις προτάσεις μου. Θα δώσω και ένα περίγραμμα μιας απλής προσέγγισης:
    Αν δεν υπήρχε η συνθήκη χ<ψ<ζ, θα είχαμε 1+2+3+...+199 = C(200,2) = 19.900 λύσεις. Αφαιρούμε τώρα 1 λύση για την τριπλή ισότητα χ=ψ=ζ=67 και 3*(100-1)=297 λύσεις για τις περιπτώσεις διπλών ισοτήτων χ=ψ#ζ, ψ=ζ#χ, ζ=χ#ψ. Μένουν 19602 λύσεις, χωρίς ισότητες, αλλά με όλες τις διατάξεις χ,ψ,ζ, ενώ εμείς θέλουμε μόνο τις χ<ψ<ζ. Οπότε 19602/3! = 3267.

    ΑπάντησηΔιαγραφή
  6. Unknown25 Νοεμβρίου 2014 στις 12:32 μ.μ.

    Για χ=1 , ψ=2 τότε έχουμε 99 λύσεις . Με την βοήθεια του excel βρίσκουμε 4355 λύσεις , δηλ ως χ= 65 , ψ= 66 , ζ=70

    ΑπάντησηΔιαγραφή
  7. RIZOPOULOS GEORGIOS25 Νοεμβρίου 2014 στις 12:46 μ.μ.

    Χριστόφορε, ξαναδές αν θέλεις τούς υπολογισμούς σου.
    Ας πούμε, ο μεγαλύτερος αποδεκτός x είναι το 66 ,τιμή για την οποία προκύπτει μία αποδεκτή τριάδα:
    66+67+68=201.
    γαι x= 65 έχουμε:{y,z}:(66,70 / 67,79, 68/68 δεν κάνει) 2 τριάδες
    x=64 (65,72/66,71/67,70,68/69) ---4 τριάδες λύσεων
    x=63 (64,74/65,73/66,72/67,71/68,70)---5 τριάδες λύσεων
    και ούτω καθεξής.
    1+2+4+5+7+8+... (66 όροι που ακολουθούν το μοτίβο +1,+2,+1,+2...κ.λ.π.)=3267

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

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