0-1

Συντονιστές: cretanman, silouan, rek2

Λάμπρος Κατσάπας
Δημοσιεύσεις: 535
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

0-1

#1

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Κυρ Δεκ 09, 2018 11:23 pm

Θεωρούμε το σύνολο A των ακολουθιών a_1a_2...a_n όπου n=0,2,4..., a_i \in \left \{ 0,1 \right \} το οποίο κατασκευάζεται

ξεκινώντας από την ακολουθία μήκους n=0 σύμφωνα με τους δύο παρακάτω κανόνες.

1. Αν a\in A τότε 0a1 \in A και 1a0 \in A


2. Αν a\in A και b\in A τότε ab \in A.

Να αποδείξετε ότι:

a είναι μια ακολουθία μήκους n αποτελούμενη από 0,1 και ισχύει γι'αυτήν ''πλήθος 0= πλήθος 1'' τότε a \in A.



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

Re: 0-1

#2

Μη αναγνωσμένη δημοσίευση από JimNt. » Κυρ Δεκ 09, 2018 11:42 pm

Είναι άμεσο με επαγωγή στο πλήθος των ψηφίων και λίγη φαντασία για το πώς θα κολληθούν τα κομμάτια στην περίπτωση που έχουμε δύο εξωτερικά 1αρια ή δύο 0ικα.(ουσιαστικά και αυτό άμεσα προκύπτει αφού διαφορετικά θα πρέπει σε κάθε substring με αρχή ένα από τα δύο εξωτερικά να υπερτερεί το πλήθος των ψηφίων της ομάδας που έχει τα εξωτερικά, άτοπο, καθώς κάποια στιγμή ο αριθμός των δύο ομάδων εξισώνεται. (και η εξίσωση αυτή γίνεται με \pm 1) ).
τελευταία επεξεργασία από JimNt. σε Κυρ Δεκ 09, 2018 11:47 pm, έχει επεξεργασθεί 1 φορά συνολικά.


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.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8261
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: 0-1

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Δεκ 09, 2018 11:45 pm

Με προλάβανε αλλά μιας και έγραψα και τις λεπτομέρειες...

Με ισχυρή επαγωγή στο m όπου n=2m το μήκος της a.

Για m=0,1 είναι προφανές. Έστω λοιπόν ότι ισχύει για κάθε άρτιο m \leqslant k και έστω μια ακολουθία a μήκους 2k+2. Αν είναι της μορφής 0b1 ή της μορφής 1b0 τότε το b έχει ίσο πλήθος από 0 και 1 οπότε από την επαγωγική υπόθεση b \in A άρα και a \in A από τον κανόνα 1.

Αν a = 1b1 τότε για κάθε 1 \leqslant i \leqslant \leqslant 2k+1 ορίζουμε ως d_i την διαφορά του πλήθους των άσσων από το πλήθος των μηδενικών που βρίσκονται στους πρώτους i όρους της ακολουθίας. Είναι d_1 = 1 και d_{2k+1} = -1. Επίσης |d_{i+1}-d_i| = 1 άρα από διακριτή συνέχεια θα υπάρχει i με d_i = 0. Προφανώς αυτό το i είναι άρτιο, έστω i = 2r. Έστω c η ακολουθία των πρώτων 2r όρων και d η ακολουθία των υπόλοιπων όρων. Στην c έχουμε ίσο πλήθος από 0 και 1, άρα το ίδιο ισχύει και για την d. Από την επαγωγική υπόθεση είναι c,d \in A, άρα και a = cd \in A από τον κανόνα 2.

Ομοίως και αν a = 0b0.


Απάντηση

Επιστροφή σε “Θεωρία Αριθμών - Προχωρημένο Επίπεδο (Seniors)”

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

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