Προβλήματα Μαθηματικών

Μαΐου 7, 2008

Ταιριάσματα και πάλι

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 10:05 μμ

Στο επίπεδο θεωρούμε το σύνολο A = {\mathbb Z}^2 όλων των ακέραιων σημείων και το σύνολο B = R A, όπου R είναι ο τελεστής στροφής κατά γωνία θ γύρω από το (0,0).

Είναι δηλ. το σύνολο B μια στροφή του A γύρω από το (0,0):

B = \{Rx:\ x \in A\}.

Δείξτε ότι υπάρχει μια σταθερά C < \infty και μια 1-1 και επί απεικόνιση f:A \to B τέτοια ώστε

|x-f(x)| \le C, για κάθε x \in A.

Advertisements

7 Σχόλια »

  1. Υπόδειξη:

    Χρησιμοποείστε όσα μάθατε στο post ταιριάσματα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 30, 2008 @ 9:42 μμ

  2. Ταυτίζοντας το \mathbb{R}^2 με το \mathbb{C} ο τελεστής R γράφετε σαν Rx=e^{i\theta}x. Άρα |Rx-Ry|=|e^{i\theta}(x-y)|=|x-y|\;\forall x,y\in \mathbb{R}^2 \;\;(\ast).
    Σύμφωνα με το πρόβλημα ‘Ταιριάσματα’ αρκεί να βρούμε σταθερά C<\infty και 1-1 απεικονίσεις g:A\longrightarrow B\;\;,\;\; h:B\longrightarrow A έτσι ώστε |g(a)-a|\le C \; , \; \; |h(b)-b|\le C \; , \; \; \forall a\in A , \; b\in B .
    Έστω B=\{b_1,b_2,\ldots,b_n,\ldots\} μια αρίθμηση του B και D_i = \{ a \in A : |b_i-a| \le \frac{\sqrt {2} } {2} \} . Τότε D_i \neq \emptyset \;\; \forall i και από το (\ast)\;\;\; D_i\cap D_j = \emptyset \;\;\forall i\neq j αφού το τελευταίο ισχύει στο \mathbb{Z}^2. Άρα \forall I\subseteq \mathbb{N} \; , \; \; Card( \cup_{i\in I}D_i) \ge Card( I ) το οποίο είναι η συνθήκη του Hall. Άρα από το (γενικευμένο) θεώρημα του Γάμου υπάρχουν a_i\in D_i\;,\;\;i\in \mathbb{N} διαφορετικά ανά δύο.
    Ορίζουμε την h:B\longrightarrow A με h(b_i)=a_i. Με τον ίδιο τρόπο ορίζετε και η g:A\longrightarrow B.

    Μου αρέσει!

    Σχόλιο από pamp0s — Μαΐου 15, 2010 @ 11:04 μμ

  3. pamp0s:

    Δεν ισχύει ότι D_i\cap D_j = \emptyset \;\;\forall i\neq j. Ένας τρόπος να δεις ότι κάτι τέτοιο δεν ισχύει (πέρα από το να βρείς δύο ακέραια σημεία που οι κύκλοι γύρω τους με ακτίνα \sqrt{2}/2 τέμνονται, όπως τα σημεία (0,0) και (0,1)) είναι να παρατηρήσεις ότι το εμβαδό των χωρίων D_j είναι μεγαλύτερο του 1 ενώ η πυκνότητα των ακεραίων σημείων είναι 1, άρα και θα υπάρχουν επικαλύψεις.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 15, 2010 @ 11:13 μμ

  4. Έστω \{b_1,b_2,\ldots\} μια αρίθμηση του B και D_i=\{a\in A: |b_i-a|\leq1\}. D_i\neq \emptyset\;\; \forall i\in \mathbb{N}. Έστω I\subset \mathbb{N} πεπερασμένο και a\in \cup_{i\in I}D_i μεγίστης απόστασης από το (o,o). Επειδή το a είναι μεγίστης απόστασης από το (o,o) το D=\{b_i: |b_i-a|\leq1, i\in I\} περιέχει ένα μόνο στοιχείο έστω το b_{i_0}. Άρα το σύνολο \cup_{i\in I-\{i_0\}}D_i περιέχει τουλάχιστο ένα στοιχείο λιγότερο από το \cup_{i\in I}D_i. Άρα επαγωγικά δείχνουμε ότι Card(\cup_{i\in I}D_i) \ge Card(I) που είναι η συνθήκη του Hall. Από το θεώρημα του γάμου υπάρχουν a_i\in D_i, \; i\in \mathbb{N} διαφορετικά ανά δύο. Αν ορίσουμε h:B\longrightarrow A,\;\;h(b_i)=a_i τότε η h είναι 1-1 και ισχύει |h(b)-b|\leq 1 \forall b\in B. Με τον ίδιο τρόπο ορίζουμε και g:A\longrightarrow B. Από το post ταιριάσματα έπεται ότι υπάρχει συνάρτηση f με τις απαιτούμενες ιδιότητες.

    Μου αρέσει!

    Σχόλιο από pamp0s — Οκτώβριος 21, 2010 @ 11:53 μμ

  5. pamp0s:

    Μπορείς να εξηγήσεις την πρόταση:

    Επειδή το a είναι μεγίστης απόστασης από το (o,o) το D=\{b_i: |b_i-a|\leq1, i\in I\} περιέχει ένα μόνο στοιχείο έστω το b_{i_0};

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 22, 2010 @ 12:55 μμ

  6. Δεν μπορώ να την εξηγήσω γιατί τώρα που τη βλέπω πιο προσεκτικά είναι λάθος.

    Μου αρέσει!

    Σχόλιο από pamp0s — Οκτώβριος 22, 2010 @ 10:18 μμ

  7. pamp0s:

    Όμως η ιδέα σου είναι σωστή πέρα από αυτό το πρόβλημα. Αλλά νομίζω πως θα πρέπει να «κολλήσεις» σε κάθε σημείο του B όχι ένα δίσκο ακτίνας 1 αλλά κάποιο άλλο σύνολο που να ταιριάζει λίγο περισσότερο στη δομή των συνόλων A και B.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 23, 2010 @ 12:12 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: