Jau pirms kāda laika man no Amazona pienāca Gödel, Escher, Bach. Vakar pirmo reizi kaut nedaudz to pašķirstīju un uzdūros sekojošam uzdevumam: MI ... MU Mūsu rīcībā ir vārds MI, nepieciešams no tā iegūt vārdu MU, izmantojot 4 transformācijas likumus: (1) Ja vārds beidzas ar I, tu vari tā galā pievienot burtu U piem., MI -> MIU; MII -> MIIU (2) Tu vari atkārtot vārda daļu, kas seko burtam M: piem., MI -> MII; MIIU -> MIIUIIU; MIIUIIU ->MIIUIIUIIUIIU utt. (3) Trīs vienu otram sekojošus burtus I tu vari pārvērst par vienu burtu U piem., MIIII -> MIU; tāpat MIIII -> MUI (4) Divus vienu otram sekojošus burtus UU tu vari atmest: piem., MIUU -> MI Vai tu vari no MI izvest MU? -------------------------------- Ja gadījumā tevi interesē, kāds ir šī uzdevuma risinājums, spied:
Vakar pirms gulētiešanas pamēģināju atrisināt uz papīra, neizdevās. Tad vēl pirms gulētiešanas vairāk vai mazāk noformulēju galvā domu, ka tas nav iespējams principā. Šorīt pārbaudīju gūgles tantes viedokli un šis viedoklis guva apstiprinājumu, ka tas tiešām nav iespējams (pamatojumu gan neatradu - un patiesībā arī nemeklēju). Mēģināšu tagad zemāk ne gluži pierādīt, ka tas nav iespējams (tam man prātiņš par īsu), bet vismaz vairāk vai mazāk loģiski pamatot, kāpēc MI nevar kļūt par MU. Lai iegūtu vārdu MU, mums ir nepieciešams iegūt vārdu, kurā nebūtu neviena burta I (jo vārdā MU šādu burtu nav) - tas būtu acīmredzami. Tā kā vārdā MI burts I ir pārstāvēts, tātad mums no I būs jāatbrīvojas. Ir tikai viens likums (3), kas atļauj atbrīvoties no burtiem I. Līdz ar to skaidrs, ka burtu I likvidēšanai būs jāizmanto tikai un vienīgi šis likums. Likums (3) atļauj katrā reizē atbrīvoties no trim burtiem I. Tātad, lai varētu no šiem burtiem tikt vaļā, ir jāpanāk, ka burti I vārdā būtu pārstāvēti skaitā n*3, kur n - patvaļīgs naturāls skaitlis. Pretējā gadījumā visu saīsināšanu rezultātā allaž atliks viens vai divi "nelikvidēti" burti I. Iegūt jaunus I burtus mēs varam tikai ar vienu likumu - numur (2). Tā kā tas divkāršo jebkuru burtu virkni (neskaitot sākuma burtu M), tad šī likuma pielietošanas rezultātā burtu I skaits pieaug sekojošā veidā: count(I(x+1))=count(I(x))*2, proti, katru reizi burtu I skaits tiek divkāršots. Tā kā sākumā mūsu rīcībā ir 1 burts I, proti, mūsu rīcībā esošais I burtu skaits nedalās ar trīs, tad šādā veidā mēs nekad neiegūsim tādu burtu I skaitu, kas būtu skaitļa trīs daudzkārtnis, bet gan tikai I skaitu 2 pakāpē n - kam loģiskā kārtā vienīgais pirmreizinātājs ir skaitlis 2. Vai kombinējot likumus (2) un (3) mēs varam iegūt tādu burtu I skaitu, kas dalītos ar 3? Piemēram, mēs esam "pavairojuši" burtus I līdz skaitam 16. Tad mēs varam ņemt nost 3, 6, 9,12 vai 15 burtus I, un iegūt attiecīgi 13, 10, 7, 4 vai 1 burtu I. Redzams, ka neviens no iegūtajiem skaitļiem ar 3 nedalās. Skaidrojums: no skaitļa 2n mēs varam atņemt 3*k. 2n ar trīs nedalās, to mēs jau iepriekš noskaidrojām. Tā kā 2n ar trīs nedalās, tad tas ir vai nu (3*j)+1 vai (3*j)+2. (3*j)+1 - (3*k) = 3*(j-k) + 1, kas faktiski ir tas pats, kas (3*j)+1, un loģiski, ka ar 3 nedalās. Tas pats ar (3*j)+2. Vēl viens pieejams gājiens ir - atņemt kaut kādu daļu no burtiem i un tad veikt atkal divkāršošanu. Problēma ir tajā, ka neko diži vairāk variantu no tā nerodas. Proti, mēs šādi varam iegūt skaitļus (3*j+1)n un (3*j+2)n, kuri atkal ar 3 nedalās. Un pēc analoģijas ar iepriekš aprakstīto arī (3*j+1)n - 3*k ar trīs nedalīsies. Likumi (1) un (4) nekādi burtu I skaitu neietekmē, kas ļauj secināt, ka izveidot vārdu, kurā nebūtu burtu I, ar mūsu rīcībā esošajiem izvedumu likumiem nav iespējams. Un tātad nav iespējams izveidot arī vārdu MU. Pseidopierādījuma beigas. Universitātē to varbūt par pierādījumu neatzītu (un arī uzdevums patiesībā ir triviāls), bet tas jau ir cits jautājums.
