Να βρεθεί το πλήθος ακεραίων

Συντονιστές: achilleas, emouroukos, silouan

Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1599
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Να βρεθεί το πλήθος ακεραίων

#1

Μη αναγνωσμένη δημοσίευση από Ορέστης Λιγνός » Παρ Αύγ 31, 2018 8:40 pm

Για πόσες θετικές ακέραιες τιμές του x \leqslant 1000, έχει η εξίσωση \sqrt{x}=\sqrt{a}+\sqrt{b} μία τουλάχιστον ακέραια λύση, με τους a,b επίσης θετικούς ακεραίους;


Κερδίζουμε ό,τι τολμούμε !

Λέξεις Κλειδιά:
nikkru
Δημοσιεύσεις: 338
Εγγραφή: Σάβ Δεκ 26, 2009 6:42 pm

Re: Να βρεθεί το πλήθος ακεραίων

#2

Μη αναγνωσμένη δημοσίευση από nikkru » Παρ Αύγ 31, 2018 9:56 pm

Ορέστης Λιγνός έγραψε:
Παρ Αύγ 31, 2018 8:40 pm
Για πόσες θετικές ακέραιες τιμές του x \leqslant 1000, έχει η εξίσωση \sqrt{x}=\sqrt{a}+\sqrt{b} μία τουλάχιστον ακέραια λύση, με τους a,b επίσης θετικούς ακεραίους;
Πόσοι θετικοί ακέραιοι που δεν υπερβαίνουν το 1000 διαιρούνται με τετράγωνο πρώτου;


Άβαταρ μέλους
min##
Δημοσιεύσεις: 297
Εγγραφή: Τρί Απρ 18, 2017 3:40 pm

Re: Να βρεθεί το πλήθος ακεραίων

#3

Μη αναγνωσμένη δημοσίευση από min## » Σάβ Σεπ 01, 2018 1:33 am

Ένα inclusion-exclusion είναι αρκετό και ταυτόχρονα ίσως χαοτικό-υπάρχει και πιο μαζεμένος τύπος(απαιτούνται πράξεις όμως)


Άβαταρ μέλους
min##
Δημοσιεύσεις: 297
Εγγραφή: Τρί Απρ 18, 2017 3:40 pm

Re: Να βρεθεί το πλήθος ακεραίων

#4

Μη αναγνωσμένη δημοσίευση από min## » Σάβ Σεπ 01, 2018 2:28 pm

Θα μετρηθούν οι square-free από το 1 μέχρι το 1000.
Θεωρώ σύνολα S_{i}=\left \{ \right.p_{i}^2,2p_{i}^2,3p_{i}^2,...,\left \lfloor 1000/p_{i}^2 \right \rfloor\left. \right \},με p_{1}=2,p_{2}=3,... και έστω p_{m} ο τελευταίος πρώτος το τετράγωνο του οποίου δεν υπερβαίνει το 1000(δηλαδή το 31).Από αρχή εγκλεισμού,αποκλεισμού,είναι :\left | S_{1}\cup S_{2}\cup ...S_{m} \right |=\sum_{1\leq i\leq m}^{.}\left | S_{i} \right |-\sum_{1\leq i< j\leq m}^{.}\left | S_{i}\cap S_{j} \right |+...
, όπου το αριστερό μέλος μετράει όλους τους αριθμούς μικρότερους του 1000 που διαιρούνται με τετράγωνο πρώτου.Άρα οι square-free είναι
x-\left | S_{1}\cup S_{2}\cup ...S_{m} \right |=x-\sum_{1\leq i\leq m}^{.}\left | S_{i} \right |+\sum_{1\leq i< j\leq m}^{.}\left | S_{i}\cap S_{j} \right |-....
Παρατηρώ ότι το S_{i}\cap S_{j} π.χ. αποτελείται από στοιχεία της μορφής k\cdot p_{i}^2p_{j}^2,οπότε αν ορίσω r_{i,j}=p_{i}p_{j},θα ισχύει \left | S_{i}\cap S_{j} \right |=\left \lfloor x/r_{i,j}^2 \right \rfloor.Έτσι,ψάχνω το x-\left | S_{1}\cup S_{2}\cup ...S_{m} \right |=x-\sum_{1\leq i\leq m}^{.}\left | S_{i} \right |+\sum_{1\leq i< j\leq m}^{.}\left | S_{i}\cap S_{j} \right |-...=x-\sum_{1\leq r_{i}\leq \sqrt{x})}^{.}\left \lfloor \frac{x}{r_{i}^2} \right \rfloor+\sum_{1\leq r_{i,j}\leq \sqrt{x}}^{.}\left \lfloor \frac{x}{r_{i,j}^2} \right \rfloor-....

Με άλλα λόγια,αν ξεχάσω για λίγο τα πρόσημα,για κάθε αριθμό-square-free 1\leq n\leq \sqrt{x} αυτό που κάνω είναι να υπολογίζω το \left \lfloor \frac{x}{n^2} \right \rfloor.
Παρατηρώ ότι το πρόσημο είναι θετικό για κάθε τέτοιο αριθμό που έχει άρτιο αριθμό πρώτων στην παραγοντοποίησή του και αρνητικό για κάθε τέτοιον αριθμό που έχει περιττό αριθμό πρώτων στην παραγοντοποίησή του.Για να γενικεύσω για κάθε αριθμό,θέλω μια συνάρτηση που όταν δέχεται non-square-free αριθμούς να επιστρέφει 0.Η παραπάνω περιγραφή είναι της συνάρτησης mobius,και ο τύπος παίρνει την τελική του μορφή:SqFr(x)=\sum_{k=1}^{\sqrt{x}}\mu (k)\left \lfloor \frac{x}{k^2} \right \rfloor.
Τώρα μένει να υπολογιστεί αυτό:
SqFr(1000)=\sum_{k=1}^{\left \lfloor \sqrt{1000} \right \rfloor}\mu (k)\left \lfloor \frac{1000}{k^2} \right \rfloor=1000-250-111-40+27-20+10-8-5+5+4-3-2+2+2-1+1-1-1-1=608

(Για τον υπολογισμό χρησιμοποίησα πίνακα με τις τιμές της mobius-φτιάχνεται εύκολα).Άρα ο ζητούμενος αριθμός είναι ο 1000-608=392.


Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1599
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Re: Να βρεθεί το πλήθος ακεραίων

#5

Μη αναγνωσμένη δημοσίευση από Ορέστης Λιγνός » Σάβ Σεπ 01, 2018 2:53 pm

:coolspeak: Για να μην ''φοβηθεί'' κανένας Junior από την λύση του Μίνωα, υπάρχει και πιο απλή λύση.


Κερδίζουμε ό,τι τολμούμε !
nikkru
Δημοσιεύσεις: 338
Εγγραφή: Σάβ Δεκ 26, 2009 6:42 pm

Re: Να βρεθεί το πλήθος ακεραίων

#6

Μη αναγνωσμένη δημοσίευση από nikkru » Σάβ Σεπ 01, 2018 8:24 pm

nikkru έγραψε:
Παρ Αύγ 31, 2018 9:56 pm
Ορέστης Λιγνός έγραψε:
Παρ Αύγ 31, 2018 8:40 pm
Για πόσες θετικές ακέραιες τιμές του x \leqslant 1000, έχει η εξίσωση \sqrt{x}=\sqrt{a}+\sqrt{b} μία τουλάχιστον ακέραια λύση, με τους a,b επίσης θετικούς ακεραίους;
Πόσοι θετικοί ακέραιοι που δεν υπερβαίνουν το 1000 διαιρούνται με τετράγωνο πρώτου;
.
Για να ισχύει για θετικούς ακέραιους \sqrt{x}=\sqrt{a}+\sqrt{b} ή θα είναι και οι τρεις τετράγωνα ακεραίων ή μπορούν να γραφούν ως εξής:

 \sqrt{a}+\sqrt{b}=\sqrt{x}\Leftrightarrow \sqrt{k^2a_1}+\sqrt{m^2b_1}=\sqrt{x}\Leftrightarrow \sqrt{k^2x_1}+\sqrt{m^2x_1}=\sqrt{(k+m)^2 x_1} με k,m,x_1 ακέραιοι.

Επομένως ζητάμε το πλήθος των θετικών ακεραίων που δεν υπερβαίνουν το 1000 και διαιρούνται με τετράγωνο πρώτου, δηλαδή ζητάμε τα

πολλαπλάσια των: 2^2,3^2,5^2,7^2,11^2,13^2,17^2,19^2,23^2,29^2,31^2 από 1 έως και 1000.Το πλήθος τους είναι 392 .

Η ιδέα της λύσης είναι ίδια με του min με χρήση γνώσεων Α Λυκείου (παρόμοια άσκηση η 5 της Β ομάδας στην παραγρ. 5.2 του σχολικού βιβλίου).


Απάντηση

Επιστροφή σε “Άλγεβρα - Προχωρημένο Επίπεδο (Juniors)”

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

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