forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 21 Σεπ 2017, 03:41

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 10 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 24 Σεπ 2016, 02:23 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 05 Φεβ 2008, 03:03
Δημοσ.: 417
Έστω S υποσύνολο των φυσικών αριθμών, τέτοιο ώστε το \mathbb N\setminus S να είναι άπειρο. Υποθέτουμε επίσης ότι το S είναι κλειστό ως προς την πρόσθεση: αν x,y\in S, τότε x+y\in S. Δείξτε ότι υπάρχει φυσικός n\geq 2 ο οποίος να διαιρεί κάθε στοιχείο του S.

_________________
\emptyset\not=\{\emptyset\}


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 28 Σεπ 2016, 08:34 
Χωρίς σύνδεση
Άβαταρ μέλους

Εγγραφη: 25 Φεβ 2008, 12:08
Δημοσ.: 78
Μιά γρήγορη προσέγγιση:

Άν 1\in S τότε S=\mathbb N επομένως το \mathbb N\setminus S=\emptyset.
Έστω 1\notin S και \forall a,b \in S με gcd(a,b)=d\geq 2 τότε \forall s \in S: s=dn , n\in \mathbb{N}.
Τέλος αν 1\notin S και a,b \in S με a<b και gcd(a,b)=1 τότε \exists s \in S : s=ab.
Αρκεί να δείξουμε πως υπάρχουν επίσης και οι s+1, s+2 , ... , s+(a-1). Τότε θα έχουμε δημιουργήσει a διαδοχικούς όρους που παράγουν όλους τους (επόμενους από αυτούς) φυσικούς. Τότε το \left |S\right | = \infty και \mathbb N\setminus S πεπερασμένο.

Ψάχνω λοιπόν x,y \in \mathbb N ώστε ax+by=s+k , k=1,2...,a-1. Επειδή gcd(a,b)=1 , οι διοφαντικές αυτές δίνουν λύση.
μένει να ελένξουμε αν έχουν λύση στους φυσικούς..

_________________
Σ'ένα άγριο όνειρο ξύπνησα παγωμένος,
κάποιος με ρώταγε μέσα από το μαύρο φώς:
Ποιός είναι ο δρόμος μου,αν ξέρω που πηγαίνω,
κι αν ξέρω ποιος από τους δυό μας είναι αυτός,
και ποιός εγώ;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 28 Σεπ 2016, 08:41 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 05 Φεβ 2008, 03:03
Δημοσ.: 417
graps έγραψε:
Έστω 1\notin S και \forall a,b \in S με gcd(a,b)=d\geq 2 τότε \forall s \in S: s=dn , n\in \mathbb{N}.


Εδώ το d είναι σταθερό, ή εξαρτάται από τα a, b;
Αν υπάρχει d τέτοιο ώστε, για κάθε a,b\in S, τότε {\rm gcd}(a,b)=d, αυτό συνεπάγεται ότι όλα τα στοιχεία του S είναι πολλαπλάσια του d. Αν όμως δεν υπάρχει τέτοια ομοιόμορφη επιλογή για το d?

_________________
\emptyset\not=\{\emptyset\}


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 28 Σεπ 2016, 08:46 
Χωρίς σύνδεση
Άβαταρ μέλους

Εγγραφη: 25 Φεβ 2008, 12:08
Δημοσ.: 78
καταρχάς το θεώρησα σταθερό, αν πάλι δεν είναι και υπάρχουν διαφορετικά gcd ανά δύο ας πούμε, τότε η περίπτωση αυτή εμπίπτει στον μικρότερο d που διαιρεί τους υπόλοιπους, αν δεν υπάρχει τέτοιος καθολικά τότε θα υπάρχουν τουλάχιστον 2 d με gcd=1

_________________
Σ'ένα άγριο όνειρο ξύπνησα παγωμένος,
κάποιος με ρώταγε μέσα από το μαύρο φώς:
Ποιός είναι ο δρόμος μου,αν ξέρω που πηγαίνω,
κι αν ξέρω ποιος από τους δυό μας είναι αυτός,
και ποιός εγώ;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 28 Σεπ 2016, 08:49 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 05 Φεβ 2008, 03:03
Δημοσ.: 417
Σωστά. Άρα όντως ανάγεται, προς άτοπο, στο ότι ο μέγιστος κοινός διαιρέτης όλων των x\in S είναι ίσος με 1.

Η ιδέα με τους διαδοχικούς όρους δουλεύει, θέλει όμως μια προσαρμογή.

_________________
\emptyset\not=\{\emptyset\}


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 28 Σεπ 2016, 08:51 
Χωρίς σύνδεση
Άβαταρ μέλους

Εγγραφη: 25 Φεβ 2008, 12:08
Δημοσ.: 78
τέλεια. Ρίξε άλλη προσέγγιση αν έχεις για να δω άλλες σκέψεις πάνω στο πρόβλημα αν είχες σκεφτεί κάτι διαφορετικό.

_________________
Σ'ένα άγριο όνειρο ξύπνησα παγωμένος,
κάποιος με ρώταγε μέσα από το μαύρο φώς:
Ποιός είναι ο δρόμος μου,αν ξέρω που πηγαίνω,
κι αν ξέρω ποιος από τους δυό μας είναι αυτός,
και ποιός εγώ;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 30 Σεπ 2016, 20:37 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 628
Αυτό είναι το Frobenius problem…NP -hard… Είναι γνωστό και ως coin problem

Εδώ σελίδα 96 πχ

https://www.math.upenn.edu/~wilf/gfology2.pdf

και εδώ σελίδα 53

http://www.fmf.uni-lj.si/~lavric/Santos%20-%20Number%20Theory%20for%20Mathematical%20Contests.pdf


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 01 Οκτ 2016, 06:59 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 05 Φεβ 2008, 03:03
Δημοσ.: 417
Για το γενικό πρόβλημα, ναι. Εδώ όμως δεν είναι απαραίτητο να χρησιμοποιηθεί.

Σαν υπόδειξη, υπάρχουν δύο διαδοχικοί φυσικοί που είναι στοιχεία του συνόλου (γιατί;). Χρησιμοποιόντας αυτούς τους δύο, μπορούμε να κατασκευάσουμε n\in S (ποιον;) τέτοιο ώστε, αν m\geq n, τότε m\in S.

_________________
\emptyset\not=\{\emptyset\}


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 01 Οκτ 2016, 12:38 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 29 Οκτ 2010, 01:19
Δημοσ.: 158
graps έγραψε:
καταρχάς το θεώρησα σταθερό, αν πάλι δεν είναι και υπάρχουν διαφορετικά gcd ανά δύο ας πούμε, τότε η περίπτωση αυτή εμπίπτει στον μικρότερο d που διαιρεί τους υπόλοιπους, αν δεν υπάρχει τέτοιος καθολικά τότε θα υπάρχουν τουλάχιστον 2 d με gcd=1


Έστω a,b\in \mathbb{Z} με gcd(a,b)=1.
Τότε, επειδή ο a είναι γεννήτορας της προσθετικής ομάδας \mathbb{Z}_{b} για μεγάλο k\in \mathbb{N} έχουμε kb,kb+1 \in S. // το kb+1 πιάνεται απο κάποιο πολλαπλάσιο του a.

Άρα υπάρχουν διαδοχικοί φυσικοί n,n+1 στο S.
Τώρα έχουμε:

n^2\in S
n^2+1=(n-1)n+(n+1) \in S
n^2+2=(n-2)n+2(n+1) \in S
...
(n+1)n=0n+n(n+1) \in S

κάθε φορά αφαιρώ ένα n και προσθέτω ένα n+1 άρα προχωράω +1 στην ευθεία των αριθμών μέχρι να φτάσω τελικά στο επόμενο πολλαπλάσιο του n.
Ξεκίνησα με τόσα n ώστε να με βγάλουν στη διαδρομή μου (n^2 \longrightarrow (n+1)n).
Στο εξής, θα χω και περίσσευμα.

Έτσι πηγαίνοντας απ το ένα πολλαπλάσιο του n στο επόμενο συμπεραίνουμε οτι όλοι οι φυσικοί απ το n^2 και μετά ανήκουν στοS.
Άτοπο, καθώς τότε το \mathbb{N} \setminus S είναι άπειρο.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Σύνολο φυσικών
ΔημοσίευσηΔημοσιεύτηκε: 05 Οκτ 2016, 00:54 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 628
Υπάρχουν ἀκέραιοι αριθμοί x_{1},x_{2},...,x_{n} τέτοιοι ώστε (a_{1},a_{2},...,a_{n})=a_{1}x_{1}+a_{2}x_{2}+...+a_{n}x_{n}
Αυτὀ εἰναι το γενικευμένο θεώρημα του Bezout (που είναι NP-complete)

Έστω \Sigma το σύνολο της μορφής αυτής. Η Αρχή τής καλής διάταξης μάς εξασφαλίζει ότι το σύνολο έχει ένα ελάχιστο στοιχείο, το d
Έστω ότι:
d=a_{1}x_{1}+a_{2}x_{2}+...+a_{n}x_{n}

Θα αποδείξουμε ότι αυτό το d είναι ο ΜΚΔ τών a_{1},a_{2},...,a_{n}
Απο τον ευκλείδιο αλγόριθμο έχουμε
\exists p_{i}, r_{i} : a_{i}=p_{i}d+r_{i},\ r_{i}=0 \vee r_{i}< d
Με r_{i}\neq 0 και :
r_{i}=a_{i}-p_{i}d = a_{i}-p_{i}(a_{1}x_{1}+...+a_{i}x_{i}+...+a_{n}x_{n})==
a_{1}(p_{i}x_{1})+...+a_{i}(1-p_{i}x_{i})+...+a_{n}(p_{i}x_{n}),(r\in \Sigma) \ \wedge (r< d), που αντιβαίνει την υπόθεση περι ελαχίστου στοιχείου. Άρα d|a_{i}, i=1,...,n Για κάθε b|a_{i}, i=1,...,n έχουμε τότε b|a_{i}x_{i}, i=1,...,n οπότε b|a_{1}x_{1}+a_{2}x_{2}+...+a_{n}x_{n}=d που καταδεικνύει τήν ύπαρξη των x_{1},x_{2},...,x_{n}

Τώρα, μάς ενδιαφέρει η περίπτωση που d=1 Όμως αυτό είναι σαν να λέμε ότι το S είναι ένα υπομονοειδές (αριθμητική ημιομάδα) τού \mathbb{N} πράγμα αδύνατον λόγω τού ότι το συμπλήρωμα τού S είναι άπειρον.


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 10 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

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


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

Αναζήτηση για:
Μετάβαση σε:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group