Дан­ные числа, рас­по­ло­жен­ные в по­ряд­ке воз­рас­та­ния, об­ра­зу­ют ариф­ме­ти­че­скую про­грес­сию с раз­но­стью 2. Сле­до­ва­тель­но, остат­ки от де­ле­ния на 3 у этих чисел че­ре­ду­ют­ся. Дей­стви­тель­но, если какое-то из этих чисел де­лит­ся на 3, т. е. имеет вид где то сле­ду­ю­щее за ним число есть 3+2  — и оно даёт оста­ток 2 от де­ле­ния на 3, далее идёт да­ю­щее оста­ток 1 от де­ле­ния на 3, а затем  — ко­то­рое снова де­лит­ся на 3. Таким об­ра­зом, остат­ки от де­ле­ния дан­ных чисел на 3 идут в по­ряд­ке ... 0; 2; 1; 0; 2; 1; 0 ...

Среди дан­ных нам чисел есть 44, да­ю­щие оста­ток 1 от де­ле­ния на 3 (они об­ра­зу­ют мно­же­ство

также 43 числа, де­ля­щих­ся на 3

и 43 числа, да­ю­щих оста­ток 2 от де­ле­ния на 3

Сумма трёх чисел может де­лить­ся на 3 в сле­ду­ю­щих слу­ча­ях.

1)  Все три числа дают оди­на­ко­вые остат­ки от де­ле­ния на 3. Есть спо­со­бов вы­брать 3 числа из мно­же­ства A и по спо­со­бов вы­брать 3 числа из мно­жеств B и C. В сумме по­лу­ча­ем

2)  Если не все остат­ки оди­на­ко­вы, то под­хо­дит толь­ко слу­чай, когда все три остат­ка раз­ные, т. е. мы долж­ны вы­брать по од­но­му числу из каж­до­го из мно­жеств A, B, C. По­лу­ча­ем

В сумме вы­хо­дит 119 282 спо­со­бов.

Ответ: 119 282.

Дан­ные числа, рас­по­ло­жен­ные в по­ряд­ке воз­рас­та­ния, об­ра­зу­ют ариф­ме­ти­че­скую про­грес­сию с раз­но­стью 4. Сле­до­ва­тель­но, остат­ки от де­ле­ния на 3 у этих чисел че­ре­ду­ют­ся. Дей­стви­тель­но, если какое-то из этих чисел де­лит­ся на 3, т. е. имеет вид где то сле­ду­ю­щее за ним число есть   — и оно даёт оста­ток 1 от де­ле­ния на 3, далее идёт да­ю­щее оста­ток 2 от де­ле­ния на 3, а затем ко­то­рое снова де­лит­ся на 3. Таким об­ра­зом, остат­ки от де­ле­ния дан­ных чисел на 3 идут в по­ряд­ке ... 0; 1; 2; 0; 1; 2; 0 ...

Среди дан­ных нам чисел есть 47, да­ю­щие оста­ток 1 от де­ле­ния на 3 (они об­ра­зу­ют мно­же­ство

также 46 чисел, де­ля­щих­ся на 3

и 47 чисел, да­ю­щих оста­ток 2 от де­ле­ния на 3

Сумма трёх чисел может де­лить­ся на 3 в сле­ду­ю­щих слу­ча­ях.

1)  Все три числа дают оди­на­ко­вые остат­ки от де­ле­ния на 3. Есть спо­со­бов вы­брать 3 числа из мно­же­ства B и по спо­со­бов вы­брать 3 числа из мно­жеств A и C. В сумме по­лу­ча­ем

2)  Если не все остат­ки оди­на­ко­вы, то под­хо­дит толь­ко слу­чай, когда все три остат­ка раз­ные, т. е. мы долж­ны вы­брать по од­но­му числу из каж­до­го из мно­жеств A, B, C. По­лу­ча­ем

В сумме вы­хо­дит 149 224 спо­со­бов.

Ответ: 149 224.

Легко про­ве­рить, что

сле­до­ва­тель­но, даёт такой же оста­ток при де­ле­нии на 3, что и Таким об­ра­зом,

даёт такой же оста­ток при де­ле­нии на 3, что и

(здесь от­бро­ше­ны два край­них сла­га­е­мых, рав­ные 0). Обо­зна­чим эту сумму за Ана­ло­гич­но пе­ре­хо­дим к

При­ме­нив эту про­це­ду­ру ещё 998 раз, по­лу­ча­ем, что фор­му­ла из усло­вия даёт такой же оста­ток при де­ле­нии на 3, что и

что даёт оста­ток 1 при де­ле­нии на 3.

За­ме­ним со­сед­ние буквы Р и Ц, на одну букву, на­при­мер, на букву Щ, это можно сде­лать, так как они стоят рядом. Тогда у нас остаётся 96 букв, и из них 4 буквы A и 26 буквы K.

Зна­чит, ко­ли­че­ство спо­со­бов пе­ре­ста­вить буквы в этом слове Кроме того, буквы Щ может 6ыть рас­шиф­ро­ва­на двумя спо­со­ба­ми: как РЦ, и как ЦР, что даёт нам уве­ли­че­ние ко­ли­че­ства спо­со­бов еще̄ два раза. Та ким об­ра­зом, полу чаем

Ответ:

За­ме­ним со­сед­ние буквы П и Р на одну букву, на­при­мер, на букву Щ, это можно сде­лать, так как они стоят рядом. Тогда у нас остаётся 9 букв, и из них 4 буквы О, 2 буквы В и 2 буквы Д.

Зна­чит, ко­ли­че­ство спо­со­бов пе­ре­ста­вить буквы в этом слове Кроме того, буквы Щ может быть рас­шиф­ро­ва­на двумя спо­со­ба­ми: как ПР и как РП, что даёт нам уве­ли­че­ние ко­ли­че­ства спо­со­бов ещё два раза. Таким об­ра­зом, полу чаем

Ответ:

а)  Если пе­ре­став­лять буквы в слове «АЛлах», то будет пе­ре­ста­но­вок. Если те­перь за­ме­нить боль­шие буквы на ма­лень­кие, по­лу­чит­ся один из ва­ри­ан­тов пе­ре­ста­но­вок для слова «аллах», при этом каж­дый ва­ри­ант по­лу­чит­ся по 4 раза (есть два ва­ри­ан­та, какая из букв "`а"' была боль­шой, а в каж­дом из них - два ва­ри­ан­та, какая из букв «л» была боль­шой). По­это­му ответ 30.

б)  За­ме­тим, что

Зна­чит,

в)  Из трех воз­мож­ных ва­ри­ан­тов: пра­виль­ная мо­не­та лежит гер­бом вверх, фаль­ши­вая мо­не­та лежит вверх одной или же дру­гой сто­ро­ной  — нам под­хо­дят два по­след­них. Воз­мож­ны три со­бы­тия, да­ю­щие дан­ный исход  — фаль­ши­вая лежит пер­вой сто­ро­ной вверх, фаль­ши­вая лежит вто­рой сто­ро­ной вверх или на­сто­я­щая лежит вверх гер­бом. В двух из этих ва­ри­ан­тов мо­не­та ока­зы­ва­ет­ся фаль­ши­вой, по­это­му ответ

Ответ:

а) Ко­неч­но, этот ответ сле­ду­ет из общей фор­му­лы для числа пе­ре­ста­но­вок с по­вто­ре­ни­я­ми: Од­на­ко для ре­ше­ния за­да­чи знать эту фор­му­лу со­всем не обя­за­тель­но, до­ста­точ­но про­сто на­вы­ка в ис­поль­зо­ва­нии «пра­ви­ла про­из­ве­де­ния» и зна­ком­ства с опре­де­ле­ни­ем чисел со­че­та­ний. Дей­стви­тель­но: буква «о» может сто­ять на любом из шести мест, для буквы «а» (когда «о» уже по­став­ле­на) име­ет­ся ва­ри­ан­тов, на остав­ших­ся трех ме­стах рас­по­ла­га­ют­ся буквы «б». Кста­ти го­во­ря, тот, кто про­ве­дет по­доб­ное рас­суж­де­ние, может уви­деть, что если вна­ча­ле вы­би­рать три места для букв «б», то всего ва­ри­ан­тов так что По­лу­чен­ное ра­вен­ство яв­ля­ет­ся част­ным слу­ча­ем до­ка­зы­ва­е­мо­го ана­ло­гич­ным об­ра­зом тож­де­ства ис­поль­зу­е­мо­го в сле­ду­ю­щем пунк­те.

Ответ: 60.

б)  Имеем:

Дру­гое рас­суж­де­ние ос­но­ва­но на идее про­из­во­дя­щих функ­ций. Пусть тогда так что С дру­гой сто­ро­ны, по­это­му !

в)  В ре­ше­нии ис­поль­зу­ют­ся лишь про­стей­шие по­ня­тия тео­рии ве­ро­ят­но­сти. Ве­ро­ят­ность того, что оба раза выпал герб, равна ве­ро­ят­ность вы­па­да­ния двух решек Зна­чит, ве­ро­ят­ность того, что пер­вый игрок вы­иг­ра­ет, равна

тем самым при любых чаще будет вы­иг­ры­вать он.

Ответ:

а)  Пусть x_n  — число спо­со­бов за­мо­ще­ния по­лос­ки «до­ми­нош­ка­ми». Край­няя левая до­ми­нош­ка может ле­жать так, как по­ка­за­но на ри­сун­ке, а или б, в пер­вом слу­чае име­ют­ся спо­со­бов за­мо­ще­ния остав­шей­ся по­лос­ки, во вто­ром их Зна­чит, а так как и то, рас­суж­дая по ин­дук­ции, по­лу­ча­ем, что x_n  — это n-е число Фи­бо­нач­чи.

б)  До этой фор­му­лы можно до­га­дать­ся, рас­смот­рев не­сколь­ко зна­че­ний n, и затем до­ка­зать ее по ин­дук­ции. При­ве­дем, од­на­ко, дру­гое рас­суж­де­ние.

Имеем: ко­эф­фи­ци­ент при в левой части равен сумме от­ку­да и сле­ду­ет ука­зан­ное тож­де­ство.

Ответ:

в)   Най­дем ве­ро­ят­ность того, что каж­дый раз уче­ник вы­хо­дит к доске, не по­про­сив под­нять­ся ни­ко­го из своих од­но­класс­ни­ков. В пер­вый раз учи­тель дол­жен вы­звать Алешу или Ев­ге­ния (см. рис.), ве­ро­ят­ность этого со­бы­тия равна во вто­рой  — опять-таки двух край­них (ве­ро­ят­ность  — и так далее, таким об­ра­зом с ве­ро­ят­но­стью никто ни­ко­му не по­ме­ша­ет. Ис­ко­мая ве­ро­ят­ность равна

Ответ:

а)  Левая ниж­няя клет­ка квад­ра­та может на­хо­дить­ся в узлах сетки, т. е. для ее рас­по­ло­же­ния име­ют­ся ва­ри­ан­тов. Таким об­ра­зом, всего име­ют­ся

ва­ри­ан­та.

Ответ: 204 спо­со­ба.

б)  Дво­ич­ных чисел, в ко­то­рых нулей не мень­ше, чем еди­ниц, столь­ко же, сколь­ко таких чисел, в ко­то­рых нулей не боль­ше, чем еди­ниц (за­ме­на ). Если n не­чет­но, то на­бо­ры этих типов не сов­па­да­ют, по­это­му ис­ко­мые на­бо­ры со­став­ля­ют по­ло­ви­ну всех n-по­зи­ци­он­ных дво­ич­ных чисел и их При чет­ном n по­лу­ча­ем так как нужно учесть число n  — по­зи­ци­он­ных чисел, в ко­то­рых нулей столь­ко же, сколь­ко еди­ниц.

Ответ: при не­чет­ном n и при чет­ном.

в)   Обо­зна­чим через время при­хо­да Васи, а   — Оли, Из усло­вия за­да­чи сле­ду­ет, что они встре­тят­ся, если или т. е. если

На ри­сун­ке за­штри­хо­ва­но мно­же­ство точек, ко­ор­ди­на­ты ко­то­рых удо­вле­тво­ря­ют ука­зан­ным не­ра­вен­ствам. Ис­ко­мая ве­ро­ят­ность равна от­но­ше­нию пло­ща­ди за­штри­хо­ван­ной части квад­ра­та к пло­ща­ди всего квад­ра­та, от­ку­да и по­лу­ча­ем ответ.

Ответ:

Дан­ные числа, рас­по­ло­жен­ные в по­ряд­ке воз­рас­та­ния, об­ра­зу­ют ариф­ме­ти­че­скую про­грес­сию с раз­но­стью 3. Сле­до­ва­тель­но, остат­ки от де­ле­ния на 5 у этих чисел че­ре­ду­ют­ся. Дей­стви­тель­но, если какое-то из этих чисел де­лит­ся на 5, то есть имеет вид где то сле­ду­ю­щее за ним число есть   — и оно даёт оста­ток 3 от де­ле­ния на 5, далее  — да­ю­щее оста­ток 1 от де­ле­ния на 5, затем  — да­ю­щее оста­ток 4 от де­ле­ния на 5, затем да­ю­щее оста­ток 4 от де­ле­ния на 5; на­ко­нец, сле­ду­ю­щим яв­ля­ет­ся ко­то­рое снова де­лит­ся на 5, после чего по­ря­док остат­ков по чисел на 5 идут в по­ряд­ке ... 0; 3; 1; 4; 2; 0 ...

Среди дан­ных нам 100 чисел есть по 20 чисел, да­ю­щих остат­ки 0, 1, 2, 3, 4 от де­ле­ния на 5.

Сумма двух чисел может де­лить­ся на 5 в сле­ду­ю­щих слу­ча­ях.

1)  Оба числа де­лят­ся на Всего кар­то­чек с та­ки­ми чис­ла­ми 20, и нужно вы­брать 2 них  — есть

сде­лать это.

2)  Одно из чисел даёт оста­ток 1 от де­ле­ния на 5  — тогда вто­рое долж­но да­вать оста­ток 4 от де­ле­ния на 5. Эту пару чисел можно вы­брать спо­со­ба­ми.

3)  Одно из чисел даёт оста­ток 2 от де­ле­ния на 5  — тогда вто­рое даёт оста­ток 3, и, ана­ло­гич­но вто­ро­му слу­чаю, по­лу­ча­ем 400 спо­со­бов вы­брать 2 числа. В итоге вы­хо­дит 990 спо­со­бов.

Ответ: 990.

Дан­ные числа, рас­по­ло­жен­ные в по­ряд­ке воз­рас­та­ния, об­ра­зу­ют ариф­ме­ти­че­скую про­грес­сию с раз­но­стью 2. Сле­до­ва­тель­но, остат­ки от де­ле­ния на 5 у этих чисел че­ре­ду­ют­ся. Дей­стви­тель­но, если какое-то из этих чисел де­лит­ся на 5, т. е. имеет вид где то сле­ду­ю­щее за ним число есть   — и оно даёт оста­ток 2 от де­ле­ния на 5, далее  — да­ю­щее оста­ток 4 от де­ле­ния на 5, затем да­ю­щее оста­ток 1 от де­ле­ния на 5, затем да­ю­щее оста­ток 3 от де­ле­ния на 5; на­ко­нец, сле­ду­ю­щим яв­ля­ет­ся ко­то­рое снова де­лит­ся на 5, после чего по­ря­док остат­ков по­вто­ря­ет­ся. Таким об­ра­зом, остат­ки от де­ле­ния дан­ных чисел на 5 идут в по­ряд­ке ... 0; 2; 4; 1; 3; 0 ...

Среди дан­ных нам 150 чисел есть по 30 чисел, да­ю­щих остат­ки 0, 1, 2, 3, 4 от де­ле­ния на 5.

Сумма двух чисел может де­лить­ся на 5 в сле­ду­ю­щих слу­ча­ях.

1)  Оба числа де­лят­ся на 5. Всего кар­то­чек с та­ки­ми чис­ла­ми 30, и нужно вы­брать 2 них  — есть

сде­лать это.

2)  Одно из чисел даёт оста­ток 1 от де­ле­ния на 5  — тогда вто­рое долж­но да­вать оста­ток 4 от де­ле­ния на 5. Эту пару чисел можно вы­брать спо­со­ба­ми.

3)  Одно из чисел даёт оста­ток 2 от де­ле­ния на 5  — тогда вто­рое даёт оста­ток 3, и, ана­ло­гич­но вто­ро­му слу­чаю, по­лу­ча­ем 900 спо­со­бов вы­брать 2 числа. В итоге вы­хо­дит 990 спо­со­бов.

Ответ: 2235.

Будем брать кар­точ­ки по оче­ре­ди. Воз­мож­ны не­сколь­ко слу­ча­ев в за­ви­си­мо­сти от того, какое число на­пи­са­но на пер­вой кар­точ­ке.

1)  Номер на кар­точ­ке окан­чи­ва­ет­ся на 00 (таких кар­то­чек 60 штук). Для де­ли­мо­сти суммы на 100 вто­рую кар­точ­ку надо вы­брать так, чтобы номер на ней также окан­чи­вал­ся на 00. Всего по­лу­ча­ем

2)  Ана­ло­гич­но, если номер на кар­точ­ке окан­чи­ва­ет­ся на 50 (таких кар­то­чек также 60 штук), то для де­ли­мо­сти суммы на 100 вто­рую кар­точ­ку надо вы­брать так, чтобы номер на ней окан­чи­вал­ся на 50, т. е. и здесь 1770 ва­ри­ан­тов.

3)  Номер на кар­точ­ке окан­чи­ва­ет­ся на число от 1 до 49 (таких кар­то­чек Для каж­дой из них пару можно вы­брать 60 спо­со­ба­ми (если число окан­чи­ва­ет­ся на 1, то по­дойдёт любая кар­точ­ка с чис­лом, окан­чи­ва­ю­щим­ся на 99; если число окан­чи­ва­ет­ся на 2  — любая кар­точ­ка с чис­лом, окан­чи­ва­ю­щим­ся на 98 и т. д.). Таким об­ра­зом, по­лу­ча­ем

4)  Номер на кар­точ­ке окан­чи­ва­ет­ся на число от 51 до 99. Все такие ва­ри­ан­ты были учте­ны при рас­смот­ре­нии тре­тье­го слу­чая (эти кар­точ­ки со­став­ля­ли пару кар­точ­кам, вы­бран­ным пер­во­на­чаль­но). Итого вы­хо­дит

Ответ: 179 940.

Будем брать кар­точ­ки по оче­ре­ди. Воз­мож­ны не­сколь­ко слу­ча­ев в за­ви­си­мо­сти от того, какое число на­пи­са­но на пер­вой кар­точ­ке.

1)  Номер на кар­точ­ке окан­чи­ва­ет­ся на 00 (таких кар­то­чек 50 штук). Для де­ли­мо­сти суммы на 100 вто­рую кар­точ­ку надо вы­брать так, чтобы номер на ней также окан­чи­вал­ся на 00. Всего по­лу­ча­ем

2)  Ана­ло­гич­но, если номер на кар­точ­ке окан­чи­ва­ет­ся на 50 (таких кар­то­чек также 50 штук), то для де­ли­мо­сти суммы на 100 вто­рую кар­точ­ку надо вы­брать так, чтобы номер на ней окан­чи­вал­ся на 50, т. е. и здесь 1225 ва­ри­ан­тов.

3)  Номер на кар­точ­ке окан­чи­ва­ет­ся на число от 1 до 49 (таких кар­то­чек Для каж­дой из них пару можно вы­брать 50 спо­со­ба­ми (если число окан­чи­ва­ет­ся на 1, то по­дойдёт любая кар­точ­ка с чис­лом, окан­чи­ва­ю­щим­ся на 99; если число окан­чи­ва­ет­ся на 2  — любая кар­точ­ка с чис­лом, окан­чи­ва­ю­щим­ся на 98 и т. д.). Таким об­ра­зом, по­лу­ча­ем

4)  Номер на кар­точ­ке окан­чи­ва­ет­ся на число от 51 до 99. Все такие ва­ри­ан­ты были учте­ны при рас­смот­ре­нии тре­тье­го слу­чая (эти кар­точ­ки со­став­ля­ли пару кар­точ­кам, вы­бран­ным пер­во­на­чаль­но). Итого вы­хо­дит

Ответ: 124 950.

Три точки из 33 дан­ных можно вы­брать спо­со­ба­ми. При этом тре­уголь­ник об­ра­зу­ет­ся во всех слу­ча­ях за ис­клю­че­ни­ем того, когда все три точки лежат на одной сто­ро­не тре­уголь­ни­ка. Итак, не под­хо­дят

Зна­чит, всего есть тре­уголь­ник.

Ответ: 4951.

Впи­шем дан­ный мно­го­уголь­ник K₁K₂, ...., K₂₀ в окруж­ность. Каж­дый четырёхуголь­ник с парой па­рал­лель­ных сто­рон опре­де­ля­ет­ся парой па­рал­лель­ных хорд с кон­ца­ми в точ­ках K₁K₂, ...., K₂₀.

Рас­смот­рим хорду, со­еди­ня­ю­щую две со­сед­ние вер­ши­ны мно­го­уголь­ни­ка, на­при­мер, K₆K₈. Су­ще­ству­ют ещё 9 хорд, па­рал­лель­ных ей (K₅K₈ и т. д.), т. е. по­лу­ча­ет­ся набор из 10 па­рал­лель­ных друг другу хорд. Из них можно об­ра­зо­вать пар па­рал­лель­ных от­рез­ков.

Ана­ло­гич­ные на­бо­ры мы по­лу­чим, если будем рас­смат­ри­вать все хорды, па­рал­лель­ные K₁K₂, ...., K₁₀K₁₁  — всего 10 таких на­бо­ров. Те­перь возьмём хорду, со­еди­ня­ю­щую вер­ши­ны, на­хо­дя­щи­е­ся через одну друг от друга, на­при­мер, K₆K₈ Су­ще­ству­ют ещё 8 хорд, па­рал­лель­ных ей (K₅K₉ и т. д.), т. е. по­лу­ча­ет­ся набор из 9 па­рал­лель­ных друг другу хорд. Из них можно об­ра­зо­вать пар па­рал­лель­ных от­рез­ков. Этих на­бо­ров также 10.

В итоге по­лу­ча­ем четырёхуголь­ни­ков. При таком спо­со­бе подсчёта пря­мо­уголь­ни­ки ока­за­лись учте­ны два­жды. За­ме­тим, что обе диа­го­на­ли впи­сан­но­го в окруж­ность пря­мо­уголь­ни­ка яв­ля­ют­ся диа­мет­ра­ми, всего диа­мет­ров с вер­ши­на­ми в дан­ных точ­ках 10, и таким об­ра­зом, вы­хо­дит пря­мо­уголь­ни­ков. По­лу­ча­ем четырёхуголь­ни­ков, име­ю­щих хотя бы одну пару па­рал­лель­ных сто­рон.

Ответ: 765.

Впи­шем дан­ный мно­го­уголь­ник K₁K₂, ...., K₁₆ в окруж­ность. Каж­дый четырёхуголь­ник с парой па­рал­лель­ных сто­рон опре­де­ля­ет­ся парой па­рал­лель­ных хорд с кон­ца­ми в точ­ках K₁, ...., K₁₆

Рас­смот­рим хорду, со­еди­ня­ю­щую две со­сед­ние вер­ши­ны мно­го­уголь­ни­ка, на­при­мер, Су­ще­ству­ют ещё 7 хорд, па­рал­лель­ных ей (K₅K₈, и т. д.), т. е. по­лу­ча­ет­ся набор из 8 па­рал­лель­ных друг другу хорд. Из них можно об­ра­зо­вать пар па­рал­лель­ных от­рез­ков.

Ана­ло­гич­ные на­бо­ры мы по­лу­чим, если будем рас­смат­ри­вать все хорды, па­рал­лель­ные K₁K₂, ...., K₈K₉  — всего 8 таких на­бо­ров. Те­перь возьмём хорду, со­еди­ня­ю­щую вер­ши­ны, на­хо­дя­щи­е­ся через одну друг от друга, на­при­мер, K₆K₈. Су­ще­ству­ют ещё 6 хорд, па­рал­лель­ных ей (K₅K₉ и т. д.), т. е. по­лу­ча­ет­ся набор из 7 па­рал­лель­ных друг другу хорд. Из них можно об­ра­зо­вать пар па­рал­лель­ных от­рез­ков. Этих на­бо­ров также 8. В итоге по­лу­ча­ем

четырёхуголь­ни­ков. При таком спо­со­бе подсчёта пря­мо­уголь­ни­ки ока­за­лись учте­ны два­жды. За­ме­тим, что обе диа­го­на­ли впи­сан­но­го в окруж­ность пря­мо­уголь­ни­ка яв­ля­ют­ся диа­мет­ра­ми, всего диа­мет­ров с вер­ши­на­ми в дан­ных точ­ках 8, и таким об­ра­зом, вы­хо­дит пря­мо­уголь­ни­ков. По­лу­ча­ем четырёхуголь­ни­ков, име­ю­щих хотя бы одну пару па­рал­лель­ных сто­рон.

Ответ: 364.

Впи­шем дан­ный мно­го­уголь­ник K₁K₂, ...., K₂₀ в окруж­ность. Каж­дая тра­пе­ция опре­де­ля­ет­ся парой па­рал­лель­ных хорд с кон­ца­ми в точ­ках K₁, ...., K₂₀.

Рас­смот­рим хорду, со­еди­ня­ю­щую две со­сед­ние вер­ши­ны мно­го­уголь­ни­ка, на­при­мер, K₆K₇. Су­ще­ству­ют ещё 9 хорд, па­рал­лель­ных ей (K₅K₈ и т. д.), т. е. по­лу­ча­ет­ся набор из 10 па­рал­лель­ных друг другу хорд. Из них можно об­ра­зо­вать пар па­рал­лель­ных от­рез­ков.

Ана­ло­гич­ные на­бо­ры мы по­лу­чим, если будем рас­смат­ри­вать все хорды, па­рал­лель­ные K₁K₂, ...., K₁₀K₁₁  — всего 10 таких на­бо­ров.

Те­перь возьмём хорду, со­еди­ня­ю­щую вер­ши­ны, на­хо­дя­щи­е­ся через одну друг от друга, на­при­мер, K₆K₈. Су­ще­ству­ют ещё 8 хорд, па­рал­лель­ных ей (K₅K₉ и т. д.), т. е. по­лу­ча­ет­ся набор из 9 па­рал­лель­ных друг другу хорд. Из них можно об­ра­зо­вать пар па­рал­лель­ных от­рез­ков. Этих на­бо­ров также 10.

В итоге по­лу­ча­ем четырёхуголь­ни­ков. При таком спо­со­бе подсчёта пря­мо­уголь­ни­ки ока­за­лись учте­ны два­жды. За­ме­тим, что обе диа­го­на­ли впи­сан­но­го в окруж­ность пря­мо­уголь­ни­ка яв­ля­ют­ся диа­мет­ра­ми, всего диа­мет­ров с вер­ши­на­ми в дан­ных точ­ках 10, и таким об­ра­зом, вы­хо­дит пря­мо­уголь­ни­ков. Вы­чи­тая удво­ен­ное ко­ли­че­ство пря­мо­уголь­ни­ков, по­лу­ча­ем четырёхуголь­ни­ков, име­ю­щих хотя бы одну пару па­рал­лель­ных сто­рон.

Ответ: 720.

Впи­шем дан­ный мно­го­уголь­ник K₁K₂, ...., K₁₆ в окруж­ность. Каж­дая тра­пе­ция опре­де­ля­ет­ся парой па­рал­лель­ных хорд с кон­ца­ми в точ­ках K₁, ...., K₁₆.

Рас­смот­рим хорду, со­еди­ня­ю­щую две со­сед­ние вер­ши­ны мно­го­уголь­ни­ка, на­при­мер, K₆K₇. Су­ще­ству­ют ещё 7 хорд, па­рал­лель­ных ей (K₅K₈ и т. д.), т. е. по­лу­ча­ет­ся набор из 8 па­рал­лель­ных друг другу хорд. Из них можно об­ра­зо­вать пар па­рал­лель­ных от­рез­ков.

Ана­ло­гич­ные на­бо­ры мы по­лу­чим, если будем рас­смат­ри­вать все хорды, па­рал­лель­ные K₁K₂, ...., K₈K₉  — всего 8 таких на­бо­ров.

Те­перь возьмём хорду, со­еди­ня­ю­щую вер­ши­ны, на­хо­дя­щи­е­ся через одну друг от друга, на­при­мер, K₆K₈. Су­ще­ству­ют ещё 6 хорд, па­рал­лель­ных ей (K₅K₉ и т. д.), т. е. по­лу­ча­ет­ся набор из 7 па­рал­лель­ных друг другу хорд. Из них можно об­ра­зо­вать пар па­рал­лель­ных от­рез­ков. Этих на­бо­ров также 8.

В итоге по­лу­ча­ем четырёхуголь­ни­ков. При таком спо­со­бе подсчёта пря­мо­уголь­ни­ки ока­за­лись учте­ны два­жды. За­ме­тим, что обе диа­го­на­ли впи­сан­но­го в окруж­ность пря­мо­уголь­ни­ка яв­ля­ют­ся диа­мет­ра­ми, всего диа­мет­ров с вер­ши­на­ми в дан­ных точ­ках 8, и таким об­ра­зом, вы­хо­дит пря­мо­уголь­ни­ков. Вы­чи­тая удво­ен­ное ко­ли­че­ство пря­мо­уголь­ни­ков, по­лу­ча­ем четырёхуголь­ни­ков, име­ю­щих хотя бы одну пару па­рал­лель­ных сто­рон.

Ответ: 336.

За­ме­тим, что для любых двух чисел су­ще­ству­ет ровно один сет, в ко­то­ром они встре­ча­ют­ся. Дей­стви­тель­но, тре­тье число этого сета стро­ит­ся так: в тех раз­ря­дах, где пер­вые два числа сов­па­да­ют, тре­тье число имеет такую же цифру; в раз­ря­де, где пер­вые два числа раз­ли­ча­ют­ся, тре­тье число по­лу­ча­ет остав­шу­ю­ся цифру. На­при­мер, для чисел 1231 и 1223 тре­тьим в сете будет 1212.

Назовём «упо­ря­до­чен­ным сетом» сет из трёх четырёхзнач­ных чисел с учётом их по­ряд­ка. За­ме­тим, что каж­дый не­упо­ря­до­чен­ный сет со­от­вет­ству­ет шести упо­ря­до­чен­ным:

По­это­му вме­сто ко­ли­че­ства не­упо­ря­до­чен­ных сетов можно срав­ни­вать ко­ли­че­ство упо­ря­до­чен­ных (их в 6 раз боль­ше) од­но­знач­но опре­де­ля­ет­ся упо­ря­до­чен­ной парой чисел

По­счи­та­ем ко­ли­че­ство упо­ря­до­чен­ных сетов слож­но­сти Каж­дый такой сет может на­чи­нать­ся про­из­воль­ным чис­лом a (81 ва­ри­ант). В этом числе нужно вы­брать k раз­ря­дов спо­со­бов вы­бо­ра) и в каж­дом из них за­ме­нить цифру на одну из двух от­лич­ных от неё (2^k спо­со­бов). В ре­зуль­та­те по­лу­чим число b, ко­то­рое од­но­знач­но опре­де­ля­ет сет. Итого по­лу­ча­ем упо­ря­до­чен­ных сетов слож­но­сти k.

Срав­ни­вая числа для раз­ных k, по­лу­ча­ем: Как видим, наи­боль­шее ко­ли­че­ство сетов имеет слож­ность

Ответ: боль­ше всего сетов слож­но­сти 3.

За­ме­тим, что опе­ра­ция об­ра­ти­ма. Для нечётного n по­ка­жем, что можно все мо­не­ты оди­на­ко­во ори­ен­ти­ро­вать. Разобьём мо­не­ты на груп­пы под­ряд иду­щих монет, име­ю­щих оди­на­ко­вую ори­ен­та­цию. Если групп хотя бы две, то они че­ре­ду­ют­ся, по­это­му их чётное число. Сле­до­ва­тель­но, хотя бы в одной груп­пе чётное число монет. Пе­ре­вер­нув эти мо­не­ты, мы умень­шим ко­ли­че­ство групп. По­сле­до­ва­тель­но умень­шая число групп та­ки­ми дей­стви­я­ми, мы можем сде­лать всего одну груп­пу и, зна­чит, по­вер­нуть все мо­не­ты оди­на­ко­во. Таким об­ра­зом, име­ет­ся не более двух ва­ри­ан­тов рас­по­ло­же­ния монет, ко­то­рые нель­зя по­лу­чить друг из друга. По­сколь­ку опе­ра­ция не ме­ня­ет чётность числа орлов, рас­по­ло­же­ние со всеми ор­ла­ми нель­зя пе­ре­ве­сти в рас­по­ло­же­ние со всеми реш­ка­ми. Стало быть, ва­ри­ан­тов рас­по­ло­же­ния ровно два.

Пе­рей­дем те­перь к слу­чаю чётного n. На­учим­ся пе­ре­во­дить рас­по­ло­же­ния монет в кон­фи­гу­ра­цию как можно более про­сто­го вида, а затем по­счи­та­ем ко­ли­че­ство таких про­стых кон­фи­гу­ра­ций, ко­то­рые нель­зя по­лу­чить друг из друга. От­ме­тим на окруж­но­сти точку возле любой из монет. Разобьём мо­не­ты на груп­пы под­ряд иду­щих монет, име­ю­щих оди­на­ко­вую ори­ен­та­цию. Будем пе­ре­во­ра­чи­вать груп­пы, в ко­то­рых чётное число монет, до тех пор, пока такие груп­пы не ис­чез­нут или не оста­нет­ся ровно одна груп­па. Если оста­лось не­сколь­ко групп, то они все нечётны. От­ме­тим, что если в какой-то груп­пе есть хотя бы три мо­не­ты, то две из них можно пе­ре­ки­нуть в со­сед­нюю груп­пу. Дей­стви­тель­но, это можно сде­лать за­ме­на­ми

Таким об­ра­зом, все све­дем к кон­фи­гу­ра­ции, в ко­то­рой есть одна боль­шая груп­па, а осталь­ные мо­не­ты че­ре­ду­ют­ся. Более того, можно счи­тать, что пер­вая мо­не­та боль­шой груп­пы на­хо­дит­ся возле от­ме­чен­ной точки. Таким об­ра­зом, кон­фи­гу­ра­ции раз­ли­ча­ют­ся лишь ко­ли­че­ством монет в боль­шой груп­пе и их ори­ен­та­ци­ей. Если груп­па ровно одна, то ори­ен­та­ция не имеет зна­че­ния, по­сколь­ку все мо­не­ты можно пе­ре­вер­нуть.

По­ка­жем, что все осталь­ные кон­фи­гу­ра­ции нель­зя по­лу­чить друг из друга. Дей­стви­тель­но, наша опе­ра­ция не ме­ня­ет раз­ность ко­ли­че­ства орлов на чётных ме­стах и ко­ли­че­ства орлов на нечётных ме­стах. Когда боль­шая груп­па со­сто­ит из од­но­го орла, т. е. когда все орлы стоят на нечётных ме­стах, а решки на чётных, эта раз­ность равна Уве­ли­че­ние ко­ли­че­ства орлов в боль­шой груп­пе умень­ша­ет эту раз­ность на 1, по­это­му все раз­но­сти от 0 до воз­мож­ны. Ана­ло­гич­но, когда боль­шая груп­па со­сто­ит из решек по­лу­чат­ся раз­но­сти от −1 до Итого по­лу­ча­ем раз­лич­ную кон­фи­гу­ра­цию.

Ответ: 2 ва­ри­ан­та для нечётных n и ва­ри­ант для чётных n.