Няколко интересни задачи, които никой досега не успя да реши

[lubimamp]

Да се намери остатъка на числото 2011 на степен 2011
а) при деление с 13;
б) при деление с 45.



Намерете броя на 7-цифрените естествени числа, които имат
а) поне една цифра, която е просто число;
б) точно една цифра, която е просто число;
в) поне две съседни цифри, които са прости числа.





Даден е езикът
L = {1n-та степен 0 на 2n-та степен | n принадлежи на N0}.
а) Да се докаже, че L не е автоматен език.
б) Да се докаже, че L e контекстно-свободен език.


Ще съм Ви благодарна за решение и обяснение как стават, защото вече месец и нещо не мога да го разбера напълно.

[Гост]

1
a)[tex]2011^{2011} \equiv 9^{2011}[/tex], понеже [tex]2011\equiv 9 \pmod{13}[/tex]. [tex]13[/tex] е просто и от малката теорема на Ферма [tex]a^{12}\equiv 1 \pmod{13}, (a,13)=1[/tex]. Значи [tex]a^{2011}\equiv (a^{12})^{167}a^7 \equiv a^7 \pmod{13}[/tex]. Значи [tex](9,13)=1\Rightarrow 9^{2011}\equiv 9^7\pmod{13}[/tex]. [tex]9^7 \equiv 81^3.9\equiv 3^3.9\equiv 3^5\equiv 9\pmod{13}[/tex]
б) [tex]2011 \equiv 31 \pmod{45}, 31^3\equiv 1 \pmod{45}\Rightarrow 2011^{2011}\equiv 31^{2011}\equiv (31^3)^{670}31\equiv 31[/tex]

2
a) простите числа, които са цифри са [tex]2,3,5,7[/tex]. Искаме да изберем една от тях - [tex]{4 \choose 1}=4[/tex] начина и да я поставим където и да е на [tex]7[/tex] места, т.е. [tex]{7 \choose 1}=7[/tex], а останалите [tex]6[/tex] цифри са произволни, избрани от 10-те цифри, без първата да е 0. Значи с първата нула включително имаме [tex]4x7x10^6[/tex]. Сега да махнем 1-вата да е 0. Когато е 0 останалите цифри са 5 и значи всички низове са [tex]4x7x10^5[/tex]. Окончателно [tex]4x7x10^6-4x7x10^5=4x7x9x10^5[/tex]
б) тази цифра, която е просто, избираме по 4 начина (виж а)). Можем да я сложим на 7 места. Другите 6 цифри избираме от 10-4=6 (махаме простите) начина. Значи с 0-ла отпред включително имамe [tex]4x7x6^6[/tex], с 0-ла отпред задължително са [tex]4x7x6^5[/tex] и значи броят е [tex]4x7x6x6^5[/tex]
в) тези 2 прости числа избираме от 4 и значи комбинациите са [tex]{4\choose 2}=6[/tex]. Можем да поставим 2-те цифри на [tex]7-1=6[/tex] места. Останалите 5 цифри можем да изберем по [tex]10^5[/tex] начина. Трябва да махнем случая с 0-ла отпред: [tex]6x6x10^5-6x6x10^4[/tex]