0-1

Λάμπρος Κατσάπας · #1

Θεωρούμε το σύνολο

των ακολουθιών a_1a_2...a_n

όπου

, $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ν

είναι μια ακολουθία μήκους

αποτελούμενη από 0,1

και ισχύει γι'αυτήν ''πλήθος

πλήθος

'' τότε $a \in A.$

JimNt. · #2

Είναι άμεσο με επαγωγή στο πλήθος των ψηφίων και λίγη φαντασία για το πώς θα κολληθούν τα κομμάτια στην περίπτωση που έχουμε δύο εξωτερικά

αρια ή δύο

ικα.(ουσιαστικά και αυτό άμεσα προκύπτει αφού διαφορετικά θα πρέπει σε κάθε substring με αρχή ένα από τα δύο εξωτερικά να υπερτερεί το πλήθος των ψηφίων της ομάδας που έχει τα εξωτερικά, άτοπο, καθώς κάποια στιγμή ο αριθμός των δύο ομάδων εξισώνεται. (και η εξίσωση αυτή γίνεται με $\pm 1$ ) ).

#3

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

Με ισχυρή επαγωγή στο

όπου

το μήκος της

.

Για

είναι προφανές. Έστω λοιπόν ότι ισχύει για κάθε άρτιο $m \leqslant k$ και έστω μια ακολουθία

μήκους

. Αν είναι της μορφής 0b1

ή της μορφής 1b0

τότε το

έχει ίσο πλήθος από

και

οπότε από την επαγωγική υπόθεση $b \in A$ άρα και $a \in A$ από τον κανόνα

.

Αν

τότε για κάθε $1 \leqslant i \leqslant \leqslant 2k+1$ ορίζουμε ως d_i

την διαφορά του πλήθους των άσσων από το πλήθος των μηδενικών που βρίσκονται στους πρώτους

όρους της ακολουθίας. Είναι d_1 = 1

και $d_{2k+1} = -1$ . Επίσης $|d_{i+1}-d_i| = 1$ άρα από διακριτή συνέχεια θα υπάρχει

με

. Προφανώς αυτό το

είναι άρτιο, έστω i = 2r

. Έστω

η ακολουθία των πρώτων

όρων και

η ακολουθία των υπόλοιπων όρων. Στην

έχουμε ίσο πλήθος από

και

, άρα το ίδιο ισχύει και για την

. Από την επαγωγική υπόθεση είναι $c,d \in A$ , άρα και $a = cd \in A$ από τον κανόνα

.

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

.

0-1

0-1

Re: 0-1

Re: 0-1

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