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

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

Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 792
Εγγραφή: Σάβ Μαρ 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.
Δημοσιεύσεις: 555
Εγγραφή: Παρ Μάιος 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.

If you are not sure it is magic then it probably is.
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 792
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

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

#3

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

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


Houston, we have a problem!
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2509
Εγγραφή: Πέμ Φεβ 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

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


Θρασύβουλος Οικονόμου
Φοιτητής ΗΜΜΥ ΑΠΘ
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 792
Εγγραφή: Σάβ Μαρ 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!
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2509
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

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

#7

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

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


Orestis Konstantinidis
Δημοσιεύσεις: 2
Εγγραφή: Σάβ Μάιος 05, 2018 2:22 pm

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

#8

Μη αναγνωσμένη δημοσίευση από Orestis Konstantinidis » Τετ Δεκ 12, 2018 11:37 pm

Γεια σας παιδιά,
εγώ πιστεύω πως μπορούμε να αναπαραστήσουμε έναν αριθμό σε άθροισμα έξι διαφορετικών μπορούμε να χρησιμοποιήσουμε επαναληπτικές μεταθέσεις: Δηλαδή να γράψουμε κάθε αριθμό(από τον 1976 έως τον 2017) ως άθροισμα άσων και να βάλουμε ανάμεσα τους ένα χώρισμα που θα υποδηλώνει την αλλαγή της μεταβλητής αρά αν θέσουμε σε μια τέτοια ανάλυση για παράδειγμα του 1967 θα έχουμε να μεταθέσουμε 1967 (ίδιους) άσσους και 5 (ίδια) χωρίσματα άρα \frac{(1967+5)!}{1967! \cdot 5!}. Με τον ίδιο τρόπο κάνουμε όλα τα υπόλοιπα και προσθέτουμε συνολικά


Ζητώ συγνώμη για την αργοπόρηση της απαντησής μου αλλα θέλω να τσεκάρω την ορθότητα της λύσης μου οπότε αν μπάζει από κάπου θα ήθελα να το ξέρω
τελευταία επεξεργασία από Demetres σε Πέμ Δεκ 13, 2018 10:16 am, έχει επεξεργασθεί 1 φορά συνολικά.
Λόγος: Γραφή σε LaTeX


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8176
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#9

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Δεκ 13, 2018 10:23 am

Ορέστη καλωσόρισες στο :logo:

Μερικά σχόλια

- Ο κανονισμός μας ζητάει πάντα από τα μέλη μας να γράφουν τα μαθηματικά σε \LaTeX. Αυτήν την φορά διόρθωσα την ανάρτηση. Στην αρχική σελίδα υπάρχει ανακοίνωση με αρκετούς συνδέσμους για βοήθεια στην γραφή σε \LaTeX.

- Στην ανάρτησή σου υπάρχουν διάφορα τυπογραφικά λάθη. (Δεν τα διόρθωσα.) Ο πρώτος αριθμός είναι το 1971 και όχι το 1976. Παρασύρθηκες από το 1971+5 και έγραψες 1976+5. Μετά το 1976 έγινε 1967.

- Είναι σωστά όσα γράφεις αλλά έχουν ήδη λεχθεί. Στην ανάρτηση του JimNt ο πρώτος όρος \binom{1976}{5} είναι ακριβώς αυτός που λες. Σε επόμενη ανάρτηση ο thrassos δίνει και την ίδια ουσιαστικά εξήγηση που έδωσες και εσύ.

- Διάβασε επίσης και την ανάρτηση του Σταύρου Παπαδόπουλου. Αντί να τα υπολογίσουμε όλα αυτά και να προσθέσουμε υπάρχει ακόμη ένα κολπάκι ώστε να υπολογιστεί η απάντηση απευθείας.


Orestis Konstantinidis
Δημοσιεύσεις: 2
Εγγραφή: Σάβ Μάιος 05, 2018 2:22 pm

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

#10

Μη αναγνωσμένη δημοσίευση από Orestis Konstantinidis » Παρ Δεκ 14, 2018 12:29 am

Σας ευχαριστώ πολύ και με συγχωρείται που διάβασα κάπως επιπόλαια τις λύσεις των υπόλοιπων μελών.


Απάντηση

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

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

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