Απλή!

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

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

Απλή!

#1

Μη αναγνωσμένη δημοσίευση από JimNt. » Παρ Μαρ 31, 2017 11:10 pm

Να βρείτε το πλήθος των θετικών ακεραίων \overline{abcd} με a+b+c+d=20.


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.

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

Re: Απλή!

#2

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Σάβ Απρ 01, 2017 12:56 am

JimNt. έγραψε:Να βρείτε το πλήθος των θετικών ακεραίων \overline{abcd} με a+b+c+d=20.
Θα πρέπει όλα τα ψηφία να είναι από 0 έως 9 εκτός από το a που πρέπει να είναι από 1 έως 9.

Αρχικά θα βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης a+b+c+d=20. Ισοδύναμα θα βρούμε το πλήθος των διατάξεων ενός δυαδικού αριθμού με 20 άσσους και 3 μηδενικά (που λειτουργούν ως διαχωριστικά των a, b, c και d. Έχουμε δηλαδή:

\dfrac{23!}{20!3!}=\dfrac{21 \cdot 22 \cdot 23}{6}=1771 λύσεις.

Από αυτές θα αφαιρέσουμε όσες έχουν τουλάχιστον ένα από τα a, b, c και d να είναι \geq 10. Θα πάμε με PIE:

Αν a \geq 10 τότε θέτουμε x=a-10 με x \geq 0 και η εξίσωση γίνεται:

a-10+b+c+d=10 \Leftrightarrow x+b+c+d=10

Με το ίδιο σκεπτικό έχουμε:

\dfrac{13!}{10!3!}=\dfrac{11 \cdot 12 \cdot 13}{6}=286 λύσεις.

Αν a \geq 10 και b \geq 10 τότε θέτουμε x=a-10 και y=b-10 με x \geq 0 και y \geq 0 και η εξίσωση γίνεται:

a-10+b-10+c+d=0 \Leftrightarrow x+y+c+d=0

που έχει μόνο 1 λύση.

Αν πρέπει τουλάχιστον 3 από a, b, c και d να είναι \geq 10, τότε δεν υπάρχει καμία λύση.

Άρα το πλήθος των λύσεων ώστε τουλάχιστον ένα από τα a, b, c και d να είναι \geq 10 είναι:

\displaystyle{\binom{4}{1} 286 - \binom{4}{2} 1 = 4 \cdot 286 - 6 = 1138}

Άρα το πλήθος των μη αρνητικών λύσεων της εξίσωσης a+b+c+d=20, ώστε τα a, b, c και d να είναι \leq 9, είναι:

1771-1138 = 633

Όμως από αυτές πρέπει να αφαιρέσουμε όσες είναι το a=0.

Θα βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης b+c+d=20, ώστε τα b, c και d να είναι \leq 9.

Θέτουμε b=9-x, c=9-y και d=9-z με 0\leq x, y, z \leq 9 και η εξίσωση γίνεται:

(9-x)+(9-y)+(9-z)=20\Leftrightarrow x+y+z=7

Όμως στην εξίσωση που φτάσαμε ο περιορισμός x, y, z \leq 9 ισχύει έτσι και αλλιώς, επομένως αρκεί να βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης. Έχουμε δηλαδή:

\dfrac{9!}{7!2!}=36 λύσεις.

Τελικά, έχουμε 633-36=597 λύσεις.


Houston, we have a problem!
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 1614
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

Re: Απλή!

#3

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Σάβ Απρ 01, 2017 9:16 am

Θα βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης b+c+d=20, ώστε τα b, c και d να είναι \leq 9.

Θέτουμε b=9-x, c=9-y και d=9-z με 0\leq x, y, z \leq 9 και η εξίσωση γίνεται:

(9-x)+(9-y)+(9-z)=20\Leftrightarrow x+y+z=7

Όμως στην εξίσωση που φτάσαμε ο περιορισμός x, y, z \leq 9 ισχύει έτσι και αλλιώς, επομένως αρκεί να βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης.

Δεν είναι σωστό.
π.χ b=12,c=6,d=2 είναι λύση χωρίς να πληρεί τον περιορισμό.
Εκανες κύκλο.


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

Re: Απλή!

#4

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Σάβ Απρ 01, 2017 2:43 pm

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε:
Διονύσιος Αδαμόπουλος έγραψε: Θα βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης b+c+d=20, ώστε τα b, c και d να είναι \leq 9.

Θέτουμε b=9-x, c=9-y και d=9-z με 0\leq x, y, z \leq 9 και η εξίσωση γίνεται:

(9-x)+(9-y)+(9-z)=20\Leftrightarrow x+y+z=7

Όμως στην εξίσωση που φτάσαμε ο περιορισμός x, y, z \leq 9 ισχύει έτσι και αλλιώς, επομένως αρκεί να βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης.
Δεν είναι σωστό.
π.χ b=12,c=6,d=2 είναι λύση χωρίς να πληρεί τον περιορισμό.
Εκανες κύκλο.
Κύριε Σταύρο μάλλον δεν ήταν σαφές αυτό που έγραψα!

Θέλουμε να βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης b+c+d=20, ώστε τα b, c, d \leq 9.

Με τον παραπάνω τρόπο που εφάρμοσα έφτασα στο ισοδύναμο:

Να βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης x+y+z=7, ώστε τα x, y, z \leq 9.

Όσο κι αν φαίνεται παράξενο, οι δύο εξισώσεις έχουν το ίδιο πλήθος λύσεων. Είμαι σίγουρος για αυτό γιατί μόλις το δοκίμασα με δύο προγραμματάκια σε γλώσσα C τα οποία και παραθέτω:

Για την πρώτη εξίσωση:

Κώδικας: Επιλογή όλων

int main()
{
    int x, y, z, p=0;
    for (x=0; x<=9; x++)
        for (y=0; y<=9; y++)
             for (z=0; z<=9; z++)
                if (x+y+z==20)
                    p++;
    printf("%d\n",p);
    return 0;
}
Για τη δεύτερη εξίσωση:

Κώδικας: Επιλογή όλων

int main()
{
    int x, y, z, p=0;
    for (x=0; x<=9; x++)
        for (y=0; y<=9; y++)
             for (z=0; z<=9; z++)
                if (x+y+z==7)
                    p++;
    printf("%d\n",p);
    return 0;
}
Γιατί όμως να προτιμήσω τη δεύτερη από την πρώτη εξίσωση; Ο λόγος είναι ότι η δεύτερη ισοδυναμεί με το:

Να βρούμε το πλήθος των μη αρνητικών λύσεων της εξίσωσης x+y+z=7.

Δεν χρειάζονται άλλοι περιορισμοί για τα x, y, z (αφού κανένα από αυτά δεν πρόκειται να βγει πάνω από 7) και μπορεί να λυθεί εύκολα πλέον με το γνωστό λήμμα της συνδυαστικής, δίνοντας 36 λύσεις, όσες μου δίνουν και τα δύο παραπάνω προγράμματα.

Επίσης, με ένα τρίτο πρόγραμμα που δοκίμασα:

Κώδικας: Επιλογή όλων

int main()
{
    int a, b, c, d, p=0;

    for (a=1; a<=9; a++)
        for (b=0; b<=9; b++)
             for (c=0; c<=9; c++)
                     for (d=0; d<=9; d++)
                        if (a+b+c+d==20)
                            p++;

    printf("%d\n",p);
    return 0;
}
επαλήθευσα ότι το πλήθος των λύσεων του αρχικού προβλήματος είναι 597, όσες δηλαδή βρήκα στην αρχική λύση μου.


Houston, we have a problem!
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 1614
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

Re: Απλή!

#5

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Σάβ Απρ 01, 2017 4:19 pm

Διονύση σου ζητώ ΣΥΓΝΩΜΗ που σε έβαλα σε αυτήν την ταλαιπωρία.
Προφανώς και έχεις δίκιο.
Αν κατάλαβες νόμιζα ότι αναφέρεσαι στην αρχική εξίσωση.
Το λάθος μου είναι ότι δεν το έλεγξα με το αποτέλεσμα.


Απάντηση

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

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

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