Πλήθος λύσεων

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

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

Πλήθος λύσεων

#1

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

Να υπολογιστεί το πλήθος των ακέραιων μη αρνητικών λύσεων της ανίσωσης:

1971 \leq a+b+c+d+e+f \leq 2017


Houston, we have a problem!

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

Re: Πλήθος λύσεων

#2

Μη αναγνωσμένη δημοσίευση από JimNt. » Σάβ Απρ 22, 2017 5:41 pm

τελευταία επεξεργασία από JimNt. σε Σάβ Απρ 22, 2017 5:52 pm, έχει επεξεργασθεί 2 φορές συνολικά.


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.
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 631
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Πλήθος λύσεων

#3

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

:coolspeak: , αλλά υπάρχει και κλειστός τύπος ;) .


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

Re: Πλήθος λύσεων

#4

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

Εγω θα πρότεινα
Αφού αποδείξετε με όσους τρόπους μπορείτε (υπάρχουν τουλάχιστον τρεις)
πόσες μη αρνητικές ακέραιες λύσεις έχει η εξίσωση

x_{1}+x_{2}+....x_{k}=n

όπου k\geq 1,n\geq 0

βρείτε τύπους για το πλήθος των μη αρνητικών λύσεων των εξισώσεων

x_{1}+x_{2}+....x_{k} \leq n με k\geq 1,n\geq 0

x_{1}+x_{2}+....x_{k}<n με k\geq 1,n\geq 1


thrassos
Δημοσιεύσεις: 32
Εγγραφή: Παρ Νοέμ 11, 2016 8:06 pm

Re: Πλήθος λύσεων

#5

Μη αναγνωσμένη δημοσίευση από thrassos » Σάβ Απρ 22, 2017 10:09 pm

Καλησπέρα κύριε Σταύρο,
Θα δώσω μία λύση για το πρώτο πρόβλημα που θέτετε.
Αρχικά, αναπαριστούμε κάθε άθροισμα x_{1} + ..... +x_{m} μη αρνητικών ακεραίων με μια ακολουθία
από x_{1} τελείες (•) ακολουθούμενες από μία κάθετη γραμμή (|), μετά από x_{2} τελείες
ακόμη μία κάθετη γραμμή και συνεχίζοντας έτσι μέχρι να τοποθετήσουμε και τις τελευταίες x_{m} τελείες (χωρίς αυτές να ακολουθούνται από κάθετη γραμμή).
Έτσι, στο τέλος θα προκύψει μια ακολουθία από n τελείες και m-1 κάθετες γραμμές.Επειδή όμως μιλάμε για μη αρνητικούς αυτό σημαίνει ότι δύο κάθετες γραμμές μπορεί να είναι κολλημένες μεταξύ τους, να μην παρεμβάλλεται δηλαδή καμία τελεία ανάμεσα τους.Άρα το πλήθος των λύσεων θα είναι όλες οι πιθανές τοποθετήσεις των κάθετων γραμμών μέσα σε αυτή την ακολουθία τελειών, δηλαδή \binom{n+m-1}{m-1}, ενώ αν μιλούσαμε για θετικούς το πλήθος των λύσεων θα ήταν \binom{n-1}{m-1} αφού οι περιπτώσεις του να βρίσκονται δύο κάθετες γραμμές κολλητά αποκλείονται.

Υ.Γ
Αντι για k χρησιμοποιω n

Φιλικά,
Θράσος


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

Re: Πλήθος λύσεων

#6

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Τετ Απρ 26, 2017 11:25 pm

Για να κλείνει σιγά σιγά κι αυτό το θέμα:
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: πόσες μη αρνητικές ακέραιες λύσεις έχει η εξίσωση

x_{1}+x_{2}+....x_{k}=n

όπου k\geq 1,n\geq 0
Είναι γνωστό λήμμα και το είδαμε και παραπάνω ότι το πλήθος λύσεων είναι:

\dbinom{n+k-1}{k-1}
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: το πλήθος των μη αρνητικών λύσεων της

x_{1}+x_{2}+....x_{k} \leq n με k\geq 1,n\geq 0
Υπάρχουν δύο τρόποι προσέγγισης.

Ας δούμε πρώτα τον ... μακρύ τρόπο:

Βρίσκουμε τα πλήθη των εξισώσεων :

x_{1}+x_{2}+....x_{k} = 0
x_{1}+x_{2}+....x_{k} = 1

\vdots

x_{1}+x_{2}+....x_{k} = n-1
x_{1}+x_{2}+....x_{k} = n

... και τα προσθέτουμε αντίστοιχα:

\dbinom{k-1}{k-1}+\dbinom{k}{k-1}+\dbinom{k+1}{k-1}+\ldots+\dbinom{n+k-1}{k-1} = \dbinom{n+k}{k}

(το τελευταίο είναι η γνωστή ταυτότητα Hockey-stick της συνδυαστικής)

Και ο πιο σύντομος τρόπος:

Η ανίσωση

x_{1}+x_{2}+...+x_{k} \leq n με k\geq 1,n\geq 0

έχει το ίδιο πλήθος μη αρνητικών ακέραιων λύσεων με την εξίσωση:

x_{1}+x_{2}+...+x_{k} + x_{k+1} = n

(η περίπτωση x_{k+1}=n αντιστοιχεί στην εξίσωση x_{1}+x_{2}+....x_{k} = 0, η περίπτωση x_{k+1}=n-1 αντιστοιχεί στην εξίσωση x_{1}+x_{2}+....x_{k} = 1 , κ.ο.κ.)

Έχουμε λοιπόν πλήθος λύσεων: \dbinom{n+k}{k}
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε:το πλήθος των μη αρνητικών λύσεων της
x_{1}+x_{2}+....x_{k}<n με k\geq 1,n\geq 1
ισοδυναμεί με το πλήθος των μη αρνητικών λύσεων της

x_{1}+x_{2}+....x_{k} \leq n-1

που σύμφωνα με τα παραπάνω είναι: \dbinom{n+k-1}{k}
Διονύσιος Αδαμόπουλος έγραψε:Να υπολογιστεί το πλήθος των ακέραιων μη αρνητικών λύσεων της ανίσωσης:

1971 \leq a+b+c+d+e+f \leq 2017
Επιστρέφοντας λοιπόν στην αρχική άσκηση, το πλήθος των μη αρνητικών λύσεων είναι:

\dbinom{2017+6}{6} - \dbinom{1971+6-1}{6} = \boxed{\dbinom{2023}{6} - \dbinom{1976}{6}}

όπως είχε απαντήσει πιο πάνω ο JimNt.


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

Re: Πλήθος λύσεων

#7

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

Διονύση γεια.
Πολύ σωστά αυτά που έγραψες.
Για το αρχικό πρόβλημα εκτός της απόδειξης που έγραψε ο Θράσος γνωρίζω ακόμα δύο.
Η μία με επαναληπτικούς συνδιασμούς και η άλλη με γεννήτριες συναρτήσεις.
Και οι τρεις είναι γενικά γνωστές.Πιστεύω ότι υπάρχουν και άλλες.


Απάντηση

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

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

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