Σελίδα 1 από 1

0-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.

Re: 0-1

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

Re: 0-1

Δημοσιεύτηκε: Κυρ Δεκ 09, 2018 11:45 pm
από Demetres
Με προλάβανε αλλά μιας και έγραψα και τις λεπτομέρειες...

Με ισχυρή επαγωγή στο 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.