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

Будем опи­сы­вать граф в виде по­сле­до­ва­тель­но­сти целых чисел (a₁, a₂, ..., a_n), где a_i озна­ча­ет сте­пень вер­ши­ны i. Будем на­зы­вать по­сле­до­ва­тель­ность целых чисел (a₁, a₂, ..., a_n) ре­а­ли­зу­е­мой, если су­ще­ству­ет граф, опи­са­ние ко­то­ро­го сов­па­да­ет с (a₁, a₂, ..., a_n). В усло­вии спра­ши­ва­ет­ся, ре­а­ли­зу­е­ма ли по­сле­до­ва­тель­ность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1).

За­ме­тим сле­ду­ю­щие два про­стых факта.

1.  Пусть тогда если ре­а­ли­зу­е­ма по­сле­до­ва­тель­ность (a₁, a₂, ..., a_n), то ре­а­ли­зу­е­ма и по­сле­до­ва­тель­ность

Для ре­а­ли­за­ции до­ста­точ­но от­ки­нуть вер­ши­ну с но­ме­ром i.

2.  Пусть тогда если ре­а­ли­зу­е­ма по­сле­до­ва­тель­ность (a₁, a₂, ..., a_n), то ре­а­ли­зу­е­ма и по­сле­до­ва­тель­ность

Дей­стви­тель­но, если то вер­ши­на с но­ме­ром i долж­на быть со­еди­не­на со всеми осталь­ны­ми вер­ши­на­ми, по­это­му до­ста­точ­но от­ки­нуть её и все вы­хо­дя­щие из неё рёбра.

Пред­по­ло­жим про­тив­ное и пусть по­сле­до­ва­тель­ность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1) ре­а­ли­зу­е­ма. Поль­зу­ясь фак­та­ми 1 и 2 по­сле­до­ва­тель­но по­лу­ча­ем, что тогда ре­а­ли­зу­е­мы и по­сле­до­ва­тель­но­сти

но по­сле­до­ва­тель­ность (2, 2), оче­вид­но, не ре­а­ли­зу­е­ма. Про­ти­во­ре­чие; зна­чит, наше пред­по­ло­же­ние не­вер­но и по­сле­до­ва­тель­ность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1) не ре­а­ли­зу­е­ма.

Ответ: нет, не может.

При­ве­дем дру­гое ре­ше­ние.

Ана­ло­гич­но пер­во­му ре­ше­нию введём граф. За­ме­тим, что если (d₁, d₂, ..., d_n) сте­пе­ни вер­шин не­ко­то­ро­го графа без пе­тель и крат­ных рёбер; то для каж­до­го k вы­пол­не­но не­ра­вен­ство

Дей­стви­тель­но, все рёбра, вы­хо­дя­щие из вер­шин с но­ме­ра­ми от 1 до k де­лят­ся на два типа:

1)  иду­щие в вер­ши­ны с но­ме­ра­ми от до n  — таких не боль­ше

2)  иду­щие в вер­ши­ны с но­ме­ра­ми от 1 до k  — таких не боль­ше но каж­дое мы можем по­счи­тать по два раза.

В за­да­че нас спра­ши­ва­ют, су­ще­ству­ет ли граф со сте­пе­ня­ми вер­шин (9, 8, 7, 5, 5, 3, 3, 3, 2, 1). Пред­по­ло­жим, что он су­ще­ству­ет, и вос­поль­зу­ем­ся до­ка­зан­ным утвер­жде­ни­ем для пер­вых 5 вер­шин:

про­ти­во­ре­чие.

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

Будем опи­сы­вать граф в виде по­сле­до­ва­тель­но­сти целых чисел (a₁, a₂, ..., a_n), где a_i озна­ча­ет сте­пень вер­ши­ны i. Будем на­зы­вать по­сле­до­ва­тель­ность целых чисел (a₁, a₂, ..., a_n) ре­а­ли­зу­е­мой, если су­ще­ству­ет граф, опи­са­ние ко­то­ро­го сов­па­да­ет с (a₁, a₂, ..., a_n). В усло­вии спра­ши­ва­ет­ся, ре­а­ли­зу­е­ма ли по­сле­до­ва­тель­ность (9, 7, 6, 5, 5, 3, 3, 2, 1, 1).

За­ме­тим сле­ду­ю­щие два про­стых факта.

1.  Пусть тогда если ре­а­ли­зу­е­ма по­сле­до­ва­тель­ность (a₁, a₂, ..., a_n), то ре­а­ли­зу­е­ма и по­сле­до­ва­тель­ность

Для ре­а­ли­за­ции до­ста­точ­но от­ки­нуть вер­ши­ну с но­ме­ром i.

2.  Пусть тогда если ре­а­ли­зу­е­ма по­сле­до­ва­тель­ность (a₁, a₂, ..., a_n), то ре­а­ли­зу­е­ма и по­сле­до­ва­тель­ность

Дей­стви­тель­но, если то вер­ши­на с но­ме­ром i долж­на быть со­еди­не­на со всеми осталь­ны­ми вер­ши­на­ми, по­это­му до­ста­точ­но от­ки­нуть её и все вы­хо­дя­щие из неё рёбра.

Пред­по­ло­жим про­тив­ное и пусть по­сле­до­ва­тель­ность (9, 7, 6, 5, 5, 3, 3, 2, 1, 1) ре­а­ли­зу­е­ма. Поль­зу­ясь фак­та­ми 1 и 2 по­сле­до­ва­тель­но по­лу­ча­ем, что тогда ре­а­ли­зу­е­мы и по­сле­до­ва­тель­но­сти

но по­сле­до­ва­тель­ность (2, 2), оче­вид­но, не ре­а­ли­зу­е­ма. Про­ти­во­ре­чие; зна­чит, наше пред­по­ло­же­ние не­вер­но и по­сле­до­ва­тель­ность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1) не ре­а­ли­зу­е­ма.

Ответ: нет, не может.

При­ве­дем дру­гое ре­ше­ние.

Ана­ло­гич­но пер­во­му ре­ше­нию введём граф. За­ме­тим, что если (d₁, d₂, ..., d_n) сте­пе­ни вер­шин не­ко­то­ро­го графа без пе­тель и крат­ных рёбер; то для каж­до­го k вы­пол­не­но не­ра­вен­ство

Дей­стви­тель­но, все рёбра, вы­хо­дя­щие из вер­шин с но­ме­ра­ми от 1 до k де­лят­ся на два типа:

1)  иду­щие в вер­ши­ны с но­ме­ра­ми от до n  — таких не боль­ше

2)  иду­щие в вер­ши­ны с но­ме­ра­ми от 1 до k  — таких не боль­ше но каж­дое мы можем по­счи­тать по два раза.

В за­да­че нас спра­ши­ва­ют, су­ще­ству­ет ли граф со сте­пе­ня­ми вер­шин (9, 7, 6, 5, 5, 3, 3, 2, 1, 1). Пред­по­ло­жим, что он су­ще­ству­ет, и вос­поль­зу­ем­ся до­ка­зан­ным утвер­жде­ни­ем для пер­вых 5 вер­шин:

про­ти­во­ре­чие.

Ответ: нет, не может.

За­ме­тим, что при каж­дом ходе конь ме­ня­ет цвет поля  — с бе­ло­го пе­ре­хо­дит на чер­ное, а с чер­но­го на белое. Клет­ка чер­ная, а зна­чит через любое не­чет­ное число ходов конь будет по­па­дать на белую клет­ку. Для того, чтобы обой­ти все поле, по­бы­вав на каж­дой клет­ке ровно по од­но­му разу, конь дол­жен со­вер­шить 63 хода. Но клет­ка чер­ная, зна­чит, за­вер­шить путь в этой клет­ке не по­лу­чит­ся.

Ответ: нель­зя.

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

Ответ: может (пока).

Ответ на пер­вый во­прос от­ри­ца­тель­ный, по­сколь­ку со­сед­ние ше­сте­рен­ки долж­ны вра­щать­ся в про­ти­во­по­лож­ные сто­ро­ны, а в слу­чае 11 ше­сте­ре­нок так быть не может. Сле­ду­ет об­ра­тить вни­ма­ние на то, что это лишь не­об­хо­ди­мое усло­вие, по­это­му такое рас­суж­де­ние еще не дает от­ве­та на вто­рой во­прос (а что если все ше­сте­рен­ки имеют раз­ное ко­ли­че­ство зуб­цов?). Чтобы ше­сте­рен­ки вра­ща­лись со­гла­со­ван­ным об­ра­зом, у них долж­ны сов­па­дать ли­ней­ные ско­ро­сти зуб­цов.

Ответ: не может; может.

Пред­по­ло­жим, что сде­ла­ны k ходов, тогда на столе на­хо­дит­ся (1001 − k) кам­ней в k + 1 куче. По­сколь­ку ни при каком целом k, то зна­чит, ни через какое число ходов не может ока­зать­ся, что в этой куче  — три камня.

Ответ: нет, нель­зя.

Сло­жив все эти по­пар­ные суммы, мы, с одной сто­ро­ны, по­лу­чим сумму сем­на­дца­ти не­чет­ных чисел, а с дру­гой  — удво­ен­ную сумму чисел от 1 до 17.

Ответ: нет, нель­зя.

Пред­по­ло­жим, ука­зан­ное в усло­вии раз­би­е­ние воз­мож­но. Сумма всех чисел от 1 до 100 равна 5050, сле­до­ва­тель­но, сумма чисел во мно­же­стве с мак­си­маль­ной сум­мой не мень­ше по­это­му оно со­дер­жит не мень­ше 6 чисел. По усло­вию, каж­дое из де­вя­ти остав­ших­ся мно­жеств со­дер­жит раз­лич­ное, боль­шее шести, ко­ли­че­ство чисел. Сле­до­ва­тель­но, во всех де­ся­ти мно­же­ствах со­дер­жит­ся не мень­ше чисел  — про­ти­во­ре­чие.

Ответ: нет.

Обо­зна­чим рас­став­лен­ные числа за a, b, c, d, по усло­вию Тогда

Ответ: нет, не может.

Так как квад­рат­ный трех­член имеет дей­стви­тель­ные корни, то

Рас­смот­рим 2 слу­чая:

1)  если то

имеет дей­стви­тель­ные корни;

2)  если то

Ответ: да.

Пусть точка P  — точка пе­ре­се­че­ния се­ре­дин­ных пер­пен­ди­ку­ля­ров PM и PN. Тогда от­ку­да

сле­до­ва­тель­но, тре­уголь­ни­ки APC и BPD равны по двум сто­ро­нам и углу между ними, зна­чит,

Ответ: нет.

a)  Нуж­ные куски все­гда можно по­лу­чить, на­при­мер, так. Вы­бе­рем из об­ра­зо­вав­ших­ся ча­стей ту, ко­то­рая не ко­ро­че дру­гой (и, зна­чит, не ко­ро­че 12,5 мет­ров), вы­ре­за­ем из неё 12 мет­ро­вый кусок. У нас оста­нет­ся две части, сумма длин ко­то­рых равна 13 м. По край­ней мере одна из этих ча­стей будет не ко­ро­че 6,5; вы­ре­за­ем 6-мет­ро­вый кусок и так далее. Оста­вать­ся будут пары ча­стей с сум­ма­ми длин 7 м, 4 м и 2 м, а вы­ре­зать­ся куски дли­ной 3 м, 2 м и 1 м со­от­вет­ствен­но.

б)  Если про­вод дли­ной мет­ров раз­ре­за­ли, на­при­мер, на части с дли­на­ми 0,995 м и 23,995 м, то по­лу­чить тре­бу­е­мые куски нель­зя. В самом деле, из куска 0,995 м не­воз­мож­но вы­ре­зать ни од­но­го тре­бу­е­мо­го куска, а из куска 23,995 м это сде­лать не по­лу­чит­ся, по­сколь­ку сумма длин боль­ше 23,995.

Ответ: а) можно; б) нель­зя.

За­ме­тим, что если на кар­точ­ке на­пи­са­но 1, то долж­но быть и 2; далее, если на­пи­са­но 3, то долж­но быть и 4 (так как 2 уже за­ня­то); и т. д. Сле­до­ва­тель­но, все пары чисел имеют вид и 2k, то есть сумма чисел на каж­дой кар­точ­ке имеет вид Тогда сумма на 21 кар­точ­ке долж­на иметь вид Оста­лось за­ме­тить, что не де­лит­ся на 4, то есть 2017 в таком виде не пред­став­ля­ет­ся.

Ответ: нет.

Ра­вен­ство вы­пол­ня­ет­ся при на­при­мер, при и

Ответ: нет.

За­ме­ча­ние.

На самом деле, ра­вен­ство вы­пол­ня­ет­ся толь­ко при или Дей­стви­тель­но, до­мно­жив его на и обо­зна­чив по­лу­чим Это эк­ви­ва­лент­но ра­вен­ству где левая часть рас­кла­ды­ва­ет­ся на мно­жи­те­ли:

Не­труд­но по­нять, что яв­ля­ют­ся един­ствен­ны­ми кор­ня­ми этого урав­не­ния, что со­от­вет­ству­ет

Такое по­лу­чить­ся могло, на­при­мер, для трёхчле­на и его кор­ней 1 и −1. Числа 2, −1, 0, 1, 2 как раз яв­ля­ют­ся под­ряд иду­щи­ми це­лы­ми чис­ла­ми.

Ответ: да.

Такое по­лу­чить­ся могло, на­при­мер, для трёхчле­на и его кор­ней 1 и −1. Числа −2, −1, 0, 1, 2 как раз яв­ля­ют­ся под­ряд иду­щи­ми це­лы­ми чис­ла­ми.

Ответ: да.

Легко за­ме­тить, что во­прос за­да­чи эк­ви­ва­лен­тен сле­ду­ю­ще­му: «Су­ще­ству­ют ли такие на­ту­раль­ные что зна­че­ние ука­зан­но­го в усло­вии вы­ра­же­ния от­ри­ца­тель­но?». Пре­об­ра­зу­ем умень­ша­е­мое:

По­сколь­ку

для лю­бо­го на­ту­раль­но­го a, то и От­сю­да по­лу­ча­ем, что ис­ход­ное вы­ра­же­ние все­гда не­от­ри­ца­тель­но.

Ответ: нет, не бы­ва­ют.

За­дан­ные числа яв­ля­ют­ся пятью по­сле­до­ва­тель­ны­ми на­ту­раль­ны­ми чис­ла­ми. Чет­ные числа 20 172 018 и 20 172 020 не под­хо­дят. Со­сед­ние числа все­гда вза­им­но про­стые:

Со­сед­ние не­чет­ные числа тоже все­гда вза­им­но про­стые:

Зна­чит, число 20 172 019 га­ран­ти­ро­ван­но яв­ля­ет­ся вза­им­но про­стым с осталь­ны­ми.

Оста­лось про­ве­рить числа 20 172 017 и 20 172 021. Число 20 172 021, как и число 20 172 018, де­лит­ся на 3, сле­до­ва­тель­но, оно не под­хо­дит. А вот

тоже вза­им­но про­стое с осталь­ны­ми.

Ответ: 20 172 017, 20 172 019.

По­ка­жем, что из про­ме­жут­ка от 1 до 13 000 можно вы­брать 29 на­ту­раль­ных чисел, удо­вле­тво­ря­ю­щих пра­ви­лам ло­те­реи. Возь­мем про­стое число 439 и числа вида 439k, где k от 2 до 29 вклю­чи­тель­но. Легко ви­деть, что, во-пер­вых,

то есть все 29 чисел лежат в про­ме­жут­ке от 1 до 13 000, а, во-вто­рых,

то есть даже сумма всех чисел не будет да­вать даже квад­рат ка­ко­го-либо на­ту­раль­но­го числа. Оче­вид­но, что сумма мень­ше­го ко­ли­че­ства чисел вида 439k также не будет да­вать даже квад­рат на­ту­раль­но­го числа, так как в раз­ло­же­нии этой суммы на про­стые все­гда будет участ­во­вать про­стое число 439.

Ответ: да.

Ис­ход­ное число 925 де­лит­ся на 37. За­ме­тим, что все опе­ра­ции ро­бо­та со­хра­ня­ют это свой­ство. Сле­до­ва­тель­но, числа 295 и 529, ко­то­рые не де­лят­ся на 37, не могут быть по­лу­че­ны ро­бо­том. Для осталь­ных при­ве­дем при­ме­ры по­сле­до­ва­тель­но­сти дей­ствий ро­бо­та (ре­ше­ние не един­ствен­но!):

Ответ: нет, да, да, нет, да.