За­ме­тим, что борец с но­ме­ром k может про­иг­рать толь­ко борцу с но­ме­ром или по­это­му после каж­до­го тура наи­мень­ший номер не может уве­ли­чить­ся боль­ше, чем на 2 но­ме­ра. На тур­ни­ре с 512 участ­ни­ка­ми 9 туров, сле­до­ва­тель­но, номер по­бе­ди­те­ля тур­ни­ра не пре­вос­хо­дит

Пред­по­ло­жим, что борец с но­ме­ром 19 может по­бе­дить. Тогда в пер­вом туре долж­ны вы­быть борцы с но­ме­ра­ми 1 и 2. Это воз­мож­но толь­ко если борец с но­ме­ром 1 про­иг­рал борцу с но­ме­ром 3, а борец с но­ме­ром 2 про­иг­рал борцу с но­ме­ром 4. Зна­чит, после пер­во­го тура борцы с но­ме­ра­ми 3 и 4 оста­нут­ся. Ана­ло­гич­но, после вто­ро­го тура оста­нут­ся борцы с но­ме­ра­ми 5 и 6, после тре­тье­го  — 7 и 8, ..., после вось­мо­го  — 17 и 18. Зна­чит, в по­след­нем, фи­наль­ном, бою встре­тят­ся борцы с но­ме­ра­ми 17 и 18. Про­ти­во­ре­чие с пред­по­ло­же­ни­ем, что борец с но­ме­ром 19 может по­бе­дить.

По­ка­жем, что борец с но­ме­ром 18 может по­бе­дить. Назовём бор­цов с но­ме­ра­ми боль­ши­ми 18 сла­бы­ми. Пусть в туре с но­ме­ром борец с но­ме­ром про­иг­ра­ет борцу с но­ме­ром борец с но­ме­ром про­иг­ра­ет борцу с но­ме­ром борцы с но­ме­ра­ми ..., 18 по­бе­дят каких-то сла­бых бор­цов, остав­ши­е­ся сла­бые борцы как-то сыг­ра­ют между собой. Тогда после 8 туров оста­нут­ся борцы с но­ме­ра­ми 17 и 18, и в фи­наль­ном бое борец с но­ме­ром 18 по­бе­дит.

Ответ: 18.

За­ме­тим, что борец с но­ме­ром k может про­иг­рать толь­ко борцу с но­ме­ром или по­это­му после каж­до­го тура наи­мень­ший номер не может уве­ли­чить­ся боль­ше, чем на 2 но­ме­ра. На тур­ни­ре с 256 участ­ни­ка­ми 8 туров, сле­до­ва­тель­но, номер по­бе­ди­те­ля тур­ни­ра не пре­вос­хо­дит

Пред­по­ло­жим, что борец с но­ме­ром 17 может по­бе­дить. Тогда в пер­вом туре долж­ны вы­быть борцы с но­ме­ра­ми 1 и 2. Это воз­мож­но толь­ко если борец с но­ме­ром 1 про­иг­рал борцу с но­ме­ром 3, а борец с но­ме­ром 2 про­иг­рал борцу с но­ме­ром 4. Зна­чит, после пер­во­го тура борцы с но­ме­ра­ми 3 и 4 оста­нут­ся. Ана­ло­гич­но, после вто­ро­го тура оста­нут­ся борцы с но­ме­ра­ми 5 и 6, после тре­тье­го −7 и после седь­мо­го  — 15 и 16. Зна­чит, в по­след­нем, фи­наль­ном, бою встре­тят­ся борцы с но­ме­ра­ми 15 и 16. Про­ти­во­ре­чие с пред­по­ло­же­ни­ем, что борец с но­ме­ром 17 может по­бе­дить.

По­ка­жем, что борец с но­ме­ром 16 может по­бе­дить. Назовём бор­цов с но­ме­ра­ми боль­ши­ми 16 сла­бы­ми. Пусть в туре с но­ме­ром борец с но­ме­ром про­иг­ра­ет борцу с но­ме­ром борец с но­ме­ром про­иг­ра­ет борцу с но­ме­ром борцы с но­ме­ра­ми по­бе­дят оста­нут­ся борцы с но­ме­ра­ми 15 и 16, и в фи­наль­ном бое борец с но­ме­ром 16 по­бе­дит.

Ответ: 16.

За­ме­тим, что борец с но­ме­ром k может про­иг­рать толь­ко борцу с но­ме­ром или по­это­му после каж­до­го тура наи­мень­ший номер не может уве­ли­чить­ся боль­ше, чем на 2 но­ме­ра. На тур­ни­ре с 512 участ­ни­ка­ми 9 туров, сле­до­ва­тель­но, номер по­бе­ди­те­ля тур­ни­ра не пре­вос­хо­дит

Пред­по­ло­жим, что борец с но­ме­ром 19 может по­бе­дить. Тогда в пер­вом туре долж­ны вы­быть борцы с но­ме­ра­ми 1 и 2. Это воз­мож­но толь­ко если борец с но­ме­ром 1 про­иг­рал борцу с но­ме­ром 3, а борец с но­ме­ром 2 про­иг­рал борцу с но­ме­ром 4. Зна­чит, после пер­во­го тура борцы с но­ме­ра­ми 3 и 4 оста­нут­ся. Ана­ло­гич­но, после вто­ро­го тура оста­нут­ся борцы с но­ме­ра­ми 5 и 6, после тре­тье­го −7 и после вось­мо­го −17 и 18. Зна­чит, в по­след­нем, фи­наль­ном, бою встре­тят­ся борцы с но­ме­ра­ми 17 и 18. Про­ти­во­ре­чие с пред­по­ло­же­ни­ем, что борец с но­ме­ром 19 может по­бе­дить.

По­ка­жем, что борец с но­ме­ром 18 может по­бе­дить. Назовём бор­цов с но­ме­ра­ми боль­ши­ми 18 сла­бы­ми. Пусть в туре с но­ме­ром борец с но­ме­ром про­иг­ра­ет борцу с но­ме­ром борец с но­ме­ром про­иг­ра­ет борцу с но­ме­ром борцы с но­ме­ра­ми по­бе­дят каких-то сла­бых бор­цов, остав­ши­е­ся сла­бые борцы как-то сыг­ра­ют между собой. Тогда после 8 туров оста­нут­ся борцы с но­ме­ра­ми 17 и 18, и в фи­наль­ном бое борец с но­ме­ром 18 по­бе­дит.

Ответ: 18.

а)  Име­ет­ся 5 ва­ри­ан­тов вы­бо­ра де­воч­ки и 19 маль­чи­ка (на ри­сун­ке а каж­дой клет­ке таб­ли­цы со­от­вет­ству­ет спо­соб вы­бо­ра сме­шан­ной пары).

б)  Со­ста­вим ана­ло­гич­ную таб­ли­цу (cм. ри­су­нок б). Ясно, что число раз­лич­ных пар  — это число a_n кле­ток, ле­жа­щих выше диа­го­на­ли. По­сколь­ку то Или, рас­суж­дая иначе: име­ет­ся 5 спо­со­бов вы­бо­ра пер­вой участ­ни­цы пары и че­ты­ре  — вто­рой. По­сколь­ку каж­дая пара по­яви­лась при таком спо­со­бе под­сче­та два­жды: {Аня, Соня}  =  {Соня, Аня}, то число раз­лич­ных жен­ских пар вдвое мень­ше, чем то есть равно де­ся­ти.

Рис. а

Рис. б

Ответ: а) 95 спо­со­ба­ми; б) 10 спо­со­ба­ми; в) 171 спо­со­бом.

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

Ответ: 1990 пар­тий.

По­сколь­ку все ко­ман­ды на­бра­ли раз­ное ко­ли­че­ство очков, а ни­чьих в во­лей­бо­ле не бы­ва­ет, то ко­ман­да-по­бе­ди­тель на­бра­ла 5 очков, сле­до­ва­тель­но, вы­иг­ра­ла у всех ко­манд, вклю­чая за­няв­шую вто­рое место. По­сколь­ку та на­бра­ла 4 очка, то она вы иг­ра­ла у всех осталь­ных, вклю­чая и тре­тье­го при­зе­ра, ко­то­рый, на­брав три очка и имел уже два про­иг­рыш а пер­вым двум ко­ман­дам, вы­иг­рал у ко­манд, за­няв­ших чет­вер­тое, пятое и по­след­нее места.

Ответ: ко­ман­да, за­няв­шая тре­тье место, вы иг­ра­ла у той, ко­то­рая была чет­вер­той.

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

1)  Когда При этом не­ра­вен­ство ста­но­вит­ся точ­ным, сле­до­ва­тель­но, ко­ман­ды, про­иг­рав­шие А, долж­ны про­иг­рать и всем ко­ман­дам, вы­иг­рав­шим у А. Если есть хотя бы одна такая ко­ман­да, то она одер­жа­ла не менее побед, что боль­ше, чем у А  — про­ти­во­ре­чие с вы­бо­ром А. Зна­чит, ко­ли­че­ство ко­манд в этом слу­чае не боль­ше 4, то есть в точ­но­сти равно 4. При­мер та­ко­го тур­ни­ра: А вы­иг­ра­ла у Б, В и Г, Б вы­иг­ра­ла у В, В вы­иг­ра­ла у Г, Г вы­иг­ра­ла у Б.

2)  Когда Пусть А вы­иг­ра­ла у Б и В, при этом можно счи­тать, что Б вы­иг­ра­ла у В. Если есть хотя бы две ко­ман­ды Г и Д, вы­иг­рав­шие у А, при этом Г вы­иг­ра­ла у Д, то у Г уже две по­бе­ды над А и Д и не может быть дру­гих, зна­чит, она про­иг­ра­ла ко­ман­дам Б и В. В таком слу­чае, ко­ман­ды Б и В в сумме одер­жа­ли не менее трёх побед  — Б и В на Г и Б на В а а это боль­ше числа побед у А, что про­ти­во­ре­чит усло­вию. Таким об­ра­зом, в дан­ном слу­чае может быть не более одной ко­ман­ды, вы­иг­рав­шей у А, и общее число ко­манд не может пре­вос­хо­дить 4. При­мер тур­ни­ра с 4 ко­ман­да­ми: А вы­иг­ра­ла у Б, Б вы­иг­ра­ла у В, В вы­иг­ра­ла у А, Г про­иг­ра­ла А, Б и В. Трёх ко­манд здесь быть не может, так как про­иг­рав­шие А ко­ман­ды Б и В в сумме могут одер­жать толь­ко одну по­бе­ду (между собой).

3)  Когда Число ко­манд в дан­ном слу­чае не пре­вос­хо­дит 3, так, как общее число побед в тур­ни­ре n ко­манд равно и, по прин­ци­пу Ди­ри­х­ле, одна из них одер­жа­ла не менее

побед, от­ку­да При­мер тур­ни­ра трёх ко­манд в дан­ном слу­чае оче­ви­ден: А вы­иг­ра­ла у Б, Б вы­иг­ра­ла у В, В вы­иг­ра­ла у А. Слу­чай двух ко­манд не­воз­мо­жен, так как ко­ман­да, про­иг­рав­шая А не смо­жет одер­жать ни одной по­бе­ды.

Ответ: три или че­ты­ре.

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

В слу­чае 1) в тур­ни­ре было сыг­ра­но игр, что не де­лит­ся на 4, по­это­му ответ от­ри­ца­тель­ный.

В слу­чае 2) в тур­ни­ре было сыг­ра­но игр, что де­лит­ся на 4, по­это­му ра­зум­но по­стро­ить при­мер.

При­ведём сразу два при­ме­ра, де­мон­стри­ру­ю­щих ос­нов­ные тех­ни­ки по­стро­е­ния при­ме­ров та­ко­го рода.

При­мер 1. Его удоб­но пред­ста­вить так: счи­та­ем ко­ман­ды вер­ши­на­ми пра­виль­но­го 9-уголь­ни­ка, игры  — его сто­ро­на­ми и диа­го­на­ля­ми, на ре­зуль­та­тив­ных играх на­ри­су­ем стрел­ки от про­иг­рав­шей ко­ман­ды к вы­иг­рав­шей. Сто­ро­ны 9-уголь­ни­ка при этом со­от­вет­ству­ют ни­чьим, a осталь­ные  — ре­зуль­та­тив­ным играм, причём все стрел­ки ори­ен­ти­ро­ва­ны по ча­со­вой стрел­ке. Каж­дая ко­ман­да про­иг­ра­ла 2-ой, 3-ей и 4-ой ко­ман­дам, сле­ду­ю­щим за ней по ча­со­вой стрел­ке и вы­иг­ра­ла у 2-ой, 3-ей и 4-ой ко­манд, пред­ше­ству­ю­щих ей по ча­со­вой стрел­ке, а с осталь­ны­ми двумя сде­ла­ла ничью.

При­мер 2. Разобьём участ­ни­ков тур­ни­ра на три под­груп­пы А, В и С по три ко­ман­ды. Внут­ри каж­дой под­груп­пы все игры окон­чи­лись ни­чьи­ми, ко­ман­ды из груп­пы А про­иг­ра­ли все игры ко­ман­дам из груп­пы B, ко­ман­ды из груп­пы B про­иг­ра­ли все игры ко­ман­дам из груп­пы C, ко­ман­ды из груп­пы C про­иг­ра­ли все игры ко­ман­дам из груп­пы А.

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

Ответ: 1) нет; 2) да.

Каж­дая ко­ман­да про­ве­ла на тур­ни­ре по 14 игр, при этом перед пер­вой из них она про­ве­ла 0 встреч, перед вто­рой  — одну встре­чу, ..., перед по­след­ней  — три­на­дцать игр. Всего в тур­ни­ре было сыг­ра­но игр. Для каж­дой игры в тур­ни­ре за­пи­шем пару чисел: пер­вое  — ко­ли­че­ство игр, сыг­ран­ных перед этой игрой одной из встре­ча­ю­щих­ся ко­манд, а вто­рое  — ко­ли­че­ство игр, сыг­ран­ных перед этой игрой вто­рой из встре­ча­ю­щих­ся ко­манд. Всего по­лу­чит­ся 210 чисел, ко­то­рые в со­во­куп­но­сти яв­ля­ют­ся объ­еди­не­ни­ем 15-ти копий мно­же­ства по одной копии для каж­дой ко­ман­ды. Сле­до­ва­тель­но. сумма всех этих чисел равна   — нечётна. С дру­гой сто­ро­ны, та же сумма равна сумме 105 чисел, яв­ля­ю­щих­ся сум­ма­ми чисел в парах. Зна­чит, хотя бы одна из сумм чисел в парах нечётна, что и тре­бо­ва­лось до­ка­зать.

Пусть в тур­ни­ре участ­во­ва­ло n ко­манд, причём ко­ман­да-по­бе­ди­тель вы­иг­ра­ла k мат­чей. Тогда каж­дая из остав­ших­ся ко­манд вы­иг­ра­ла по матча. Всего между ко­ман­да­ми со­сто­я­лось мат­чей, в ко­то­рых сум­мар­но было по­бе­ди­те­лей. С дру­гой сто­ро­ны, сум­мар­ное число побед всех ко­манд равно Зна­чит,

или

от­ку­да

яв­ля­ет­ся целым чис­лом, сле­до­ва­тель­но,

целое число, а зна­чит   — целое, что воз­мож­но лишь при

При мат­чей не было.

При число что не яв­ля­ет­ся целым.

При число

При­мер: за­ну­ме­ру­ем ко­ман­ды чис­ла­ми 1, 2, 3, 4. Ко­ман­да 1 вы­иг­ра­ла у всех, ко­ман­да 2 вы­иг­ра­ла и ко­ман­ды 3, ко­ман­да 3 вы­иг­ра­ла и ко­ман­ды 4, ко­ман­да 4 вы­иг­ра­ла и ко­ман­ды 2.

Ответ: 4.

Каж­дый участ­ник (кроме по­бе­ди­те­ля) про­иг­рал кому-то одну пар­тию. Таких 99, зна­чит, вы­иг­рать 2 пар­тии не могло более 49 участ­ни­ков (им кто-то дол­жен про­иг­рать 2 пар­тии).

По­ка­жем, что их могло быть 49. Пусть №3 вы­иг­рал у №1 и №2, №5  — у №3 и №4,... №99  — y No97 и №98, a №100 вы­иг­рал у №99. Тогда все участ­ни­ки с не­чет­ны­ми но­ме­ра­ми (кроме пер­во­го) вы­иг­ра­ли ровно по 2 пар­тии.

Ответ: 49.

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

Ответ: 3.

Вве­дем обо­зна­че­ния: z  — сила од­но­го же­ву­на, m  — сила од­но­го ми­гу­на. Спра­вед­ли­вы сле­ду­ю­щие не­ра­вен­ства:

Зна­чит, от­ве­ты б), в) и д) пра­виль­ные. По­ка­жем, по­че­му от­ве­ты а) и г) не могут счи­тать­ся пра­виль­ны­ми: возь­мем пару и   — для нее ис­ход­ное утвер­жде­ние верно (ко­ман­да из 7 же­ву­нов, об­ла­да­ю­щая сум­мар­ной силой по­бе­дит ко­ман­ду из 8 ми­гу­нов, об­ла­да­ю­щую сум­мар­ной силой и при этом ко­ман­да из 7 ми­гу­нов по­бе­дит ко­ман­ду из 6 же­ву­нов, а ко­ман­да из 11 ми­гу­нов по­бе­дит ко­ман­ду из 9 же­ву­нов; од­на­ко, для пары и ис­ход­ное утвер­жде­ние также верно, но ис­хо­ды двух дру­гих встреч про­ти­во­по­лож­ны.

Ответ: б), в) и д).

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

Пусть z  — сила од­но­го же­ву­на, m  — сила од­но­го ми­гу­на; и Мно­же­ство точек плос­ко­сти, удо­вле­тво­ря­ю­щих усло­вию   — это точки, ле­жа­щие выше оси z, но стро­го ниже пря­мой за­да­ва­е­мой урав­не­ни­ем

Пусть у нас x же­ву­нов и y ми­гу­нов. Ре­зуль­тат можно пред­ска­зать тогда и толь­ко тогда, когда пря­мая с уг­ло­вым ко­эф­фи­ци­ен­том лежит не ниже ℓ₀ то есть или На­при­мер, в пунк­те б) мы по­лу­чим вер­ное не­ра­вен­ство а в пунк­те а)  — не­вер­ное не­ра­вен­ство

Вза­им­ное рас­по­ло­же­ние пря­мой ℓ₀ и пря­мых с уг­ло­вы­ми ко­эф­фи­ци­ен­та­ми, ука­зан­ны­ми в ва­ри­ан­тах от­ве­тов, при­ве­де­но на ри­сун­ке.

При­мер. Усло­вию за­да­чи, оче­вид­но, удо­вле­тво­ря­ют числа так как при любом на­ту­раль­ном k число де­лит­ся как на так и на

Оцен­ка. Пусть a, b, c  — три под­ряд иду­щих числа в стро­ке, но не пер­вые три числа. До­ка­жем, что По усло­вию, где x и y на­ту­раль­ные. Тогда причём c де­лит­ся на

По­лу­ча­ем, что де­лит­ся на от­ку­да де­лит­ся на и так как x и вза­им­но про­сты, y де­лит­ся на то есть что и тре­бо­ва­лось.

За­ме­тим, что пер­вые два числа не мень­ше 1 каж­дое. Тре­тье число боль­ше вто­ро­го (так как де­лит­ся на сумму вто­ро­го и пер­во­го), а зна­чит, хотя бы в два раза боль­ше вто­ро­го (так как де­лит­ся на него и не равно ему). По до­ка­зан­но­му выше, четвёртое число тогда хотя бы в 3 раза боль­ше тре­тье­го, пятое  — хотя бы в 3 раза боль­ше четвёртого, и так далее, от­ку­да по ин­дук­ции по­лу­ча­ем, что k-е число не мень­ше, чем при всех на­ту­раль­ных

Ответ: 2019!.

а) Оче­вид­но,   — наи­мень­шее число слож­но­сти k. По­это­му все числа между и имеют слож­ность не боль­ше k. Пусть n  — не сте­пень двой­ки. Тогда между n и есть сте­пень двой­ки (можно взять наи­боль­шую сте­пень двой­ки, мень­шую n, и удво­ить её). Оче­вид­но, её слож­ность боль­ше, чем у

б) В силу пунк­та а), до­ста­точ­но рас­смот­реть слу­чай где k на­ту­раль­ное. Но число имеет такую же слож­ность, как и n, и на­хо­дит­ся между n и

Для зна­то­ков. Утвер­жде­ние б) сле­ду­ет из по­сту­ла­та Бер­тра­на: если p  — про­стое число, то сле­ду­ю­щее про­стое мень­ше 2p. Дей­стви­тель­но, пред­ста­вим n в виде pr, где p  — про­стое, r  — на­ту­раль­ное. Пусть q  — сле­ду­ю­щее за p про­стое число. Тогда а слож­ность qr равна слож­но­сти n.

Ответ: а) Для б) таких чисел нет.

I спо­соб. (А. Ша­по­ва­лов) Назовём си­ту­а­цию по­бед­ной, если про­ве­де­но не более чем взве­ши­ва­ние и опре­де­ле­ны веса k монет, причём среди них есть се­реб­ря­ная или две мед­ных. В по­бед­ной си­ту­а­ции, срав­ни­вая не­из­вест­ную мо­не­ту с весом 2 г, мы опре­де­лим её вес, уве­ли­чив число из­вест­ных монет и число взве­ши­ва­ний на еди­ни­цу и так опре­де­лим все мо­не­ты не более чем за 101 взве­ши­ва­ние.

В каж­дый мо­мент будем срав­ни­вать число за­тро­ну­тых (участ­во­вав­ших во взве­ши­ва­ни­ях) монет чис­лом взве­ши­ва­ний Сна­ча­ла вы­де­лим одну мо­не­ту и будем срав­ни­вать не­за­тро­ну­тые мо­не­ты с ней, пока не найдём мо­не­ту дру­го­го веса. Пусть A более лёгкая, а B  — более тяжёлая из за­тро­ну­тых монет. Далее срав­ни­ва­ем не­за­тро­ну­тые мо­не­ты с B, пока снова не по­лу­чим не­ра­вен­ство. Те­перь у нас есть одна или не­сколь­ко монет оди­на­ко­во­го веса a, одна или не­сколь­ко монет дру­го­го веса и одна мо­не­та C веса Срав­ним C с A. Воз­мож­ны два слу­чая.

1)  Если Срав­ним B с то есть b с Воз­мож­ны ва­ри­ан­ты: (если Во всех слу­ча­ях си­ту­а­ция по­бед­ная: веса z монет опре­де­ле­ны и есть нуж­ные мо­не­ты (с общим весом 2).

2)  Если Зна­чит, a, b, c  — три раз­ных веса, они как-то упо­ря­до­че­ны или по­это­му опре­де­ле­ны од­но­знач­но. При этом   — си­ту­а­ция по­бед­ная.

За­ме­ча­ние. При опре­де­лен­ных усло­ви­ях не­ко­то­рые взве­ши­ва­ния можно не про­во­дить: на­при­мер, если C тя­же­лее B, то уже если при пер­вом не­ра­вен­стве уже есть ещё мо­не­та веса a, ей можно вос­поль­зо­вать­ся как мо­не­той C.

II спо­соб. (A. Ря­би­чев) Сна­ча­ла до­ка­жем по ин­дук­ции сле­ду­ю­щее вспо­мо­га­тель­ное

утвер­жде­ние 1. Пусть есть k монет, среди ко­то­рых все три типа пред­став­ле­ны, причём про пару монет A, a уже из­вест­но, что Тогда можно опре­де­лить, какая из k монет ка­ко­го типа, за взве­ши­ва­ние.

База. Если монет три, срав­нив остав­шу­ю­ся мо­не­ту с A и с a, мы упо­ря­до­чим их по весу.

Шас. Срав­ним какие-ни­будь две мо­не­ты, кроме A и a. Если они равны, то одну можно от­бро­сить (за­пом­нив, с какой она сов­па­да­ет по весу), и вос­поль­зо­вать­ся пред­по­ло­же­ни­ем ин­дук­ции для мо­не­ты.

Если они не равны, ска­жем что по­лу­чи­лась пара Те­перь срав­ним и Если веса пар равны, то и так что мы можем вы­ки­нуть B и b (за­пом­нив, что они сов­па­да­ют по весу с A и a), и вос­поль­зо­вать­ся пред­по­ло­же­ни­ем ин­дук­ции для монет.

Пусть веса пар раз­лич­ны, для опре­делённо­сти, За­ме­тим, что при этом обя­за­тель­но и Мо­не­ты в паре имеют либо веса (2, 1), либо (2, 2), либо (3, 2). Таким об­ра­зом, срав­нив с мы од­но­знач­но вос­ста­но­вим веса всех четырёх монет. Среди них есть мо­не­та веса 2, будем срав­ни­вать с ней все осталь­ные мо­не­ты, на что уйдут остав­ши­е­ся взве­ши­ва­ния. Пер­вое утвер­жде­ние до­ка­за­но. Те­перь вы­ве­дем по ин­дук­ции сле­ду­ю­щее утвер­жде­ние, уси­ли­ва­ю­щее тре­бу­е­мое в за­да­че.

Утвер­жде­ние 2. Если есть k монет, среди ко­то­рых все три типа пред­став­ле­ны, то можно опре­де­лить, какая мо­не­та ка­ко­го типа, за k взве­ши­ва­ний.

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

Шаг. Срав­ним какие-ни­будь две мо­не­ты. Если они равны, то одну можно от­бро­сить (за­пом­нив, с какой она сов­па­да­ет по весу), и мы пе­ре­хо­дим к слу­чаю мо­не­ты, среди ко­то­рых все типы пред­став­ле­ны. Если они не равны, ска­жем что об­ра­зо­ва­лась пара и вос­поль­зу­ем­ся утвер­жде­ни­ем.

За­ме­ча­ние. Мы сде­ла­ли на одно взве­ши­ва­ние мень­ше, чем пред­по­ла­га­лось в усло­вии. Кроме того, мы ис­поль­зо­ва­ли толь­ко то, что сумма весов двух се­реб­ря­ных монет равна сумме весов мед­ной и зо­ло­той; тот факт, что се­реб­ря­ная мо­не­та вдвое тя­же­лее мед­ной, для дан­но­го ре­ше­ния не важен.

Пара хо­ро­шая. Дей­стви­тель­но,

Путь к ре­ше­нию. Есте­ствен­но по­пы­тать­ся найти такое n, что оно есть квад­рат, умно­жен­ный на m, и при этом есть квад­рат, умно­жен­ный на Тогда имеет вид Так как n, поделённое на m, тоже квад­рат, имеем:

квад­рат. Самый про­стой спо­соб это обес­пе­чить  — по­ло­жить рав­ным тогда от­ку­да

I спо­соб. (А. Ша­по­ва­лов) Назовём си­ту­а­цию по­бед­ной, если про­ве­де­но не более чем взве­ши­ва­ние и опре­де­ле­ны веса k монет, причём среди них есть се­реб­ря­ная или две мед­ных. В по­бед­ной си­ту­а­ции, срав­ни­вая не­из­вест­ную мо­не­ту с весом 2 г, мы опре­де­лим её вес, уве­ли­чив число из­вест­ных монет и число взве­ши­ва­ний на еди­ни­цу и так опре­де­лим все мо­не­ты не более чем за 101 взве­ши­ва­ние.

В каж­дый мо­мент будем срав­ни­вать число за­тро­ну­тых (участ­во­вав­ших во взве­ши­ва­ни­ях) монет чис­лом взве­ши­ва­ний Сна­ча­ла вы­де­лим одну мо­не­ту и будем срав­ни­вать не­за­тро­ну­тые мо­не­ты с ней, пока не найдём мо­не­ту дру­го­го веса. Пусть A более лёгкая, а B  — более тяжёлая из за­тро­ну­тых монет. Далее срав­ни­ва­ем не­за­тро­ну­тые мо­не­ты с B, пока снова не по­лу­чим не­ра­вен­ство. Те­перь у нас есть одна или не­сколь­ко монет оди­на­ко­во­го веса a, одна или не­сколь­ко монет дру­го­го веса и одна мо­не­та C веса Срав­ним C с A. Воз­мож­ны два слу­чая.

1)  Если Срав­ним B с то есть b с Воз­мож­ны ва­ри­ан­ты: (если Во всех слу­ча­ях си­ту­а­ция по­бед­ная: веса z монет опре­де­ле­ны и есть нуж­ные мо­не­ты (с общим весом 2).

2)  Если Зна­чит, a, b, c  — три раз­ных веса, они как-то упо­ря­до­че­ны или по­это­му опре­де­ле­ны од­но­знач­но. При этом   — си­ту­а­ция по­бед­ная.

За­ме­ча­ние. При опре­де­лен­ных усло­ви­ях не­ко­то­рые взве­ши­ва­ния можно не про­во­дить: на­при­мер, если C тя­же­лее B, то уже если при пер­вом не­ра­вен­стве уже есть ещё мо­не­та веса a, ей можно вос­поль­зо­вать­ся как мо­не­той C.

II спо­соб. (A. Ря­би­чев) Сна­ча­ла до­ка­жем по ин­дук­ции сле­ду­ю­щее вспо­мо­га­тель­ное

утвер­жде­ние 1. Пусть есть k монет, среди ко­то­рых все три типа пред­став­ле­ны, причём про пару монет A, a уже из­вест­но, что Тогда можно опре­де­лить, какая из k монет ка­ко­го типа, за взве­ши­ва­ние.

База. Если монет три, срав­нив остав­шу­ю­ся мо­не­ту с A и с a, мы упо­ря­до­чим их по весу.

Шас. Срав­ним какие-ни­будь две мо­не­ты, кроме A и a. Если они равны, то одну можно от­бро­сить (за­пом­нив, с какой она сов­па­да­ет по весу), и вос­поль­зо­вать­ся пред­по­ло­же­ни­ем ин­дук­ции для мо­не­ты.

Если они не равны, ска­жем что по­лу­чи­лась пара Те­перь срав­ним и Если веса пар равны, то и так что мы можем вы­ки­нуть B и b (за­пом­нив, что они сов­па­да­ют по весу с A и a), и вос­поль­зо­вать­ся пред­по­ло­же­ни­ем ин­дук­ции для монет.

Пусть веса пар раз­лич­ны, для опре­делённо­сти, За­ме­тим, что при этом обя­за­тель­но и Мо­не­ты в паре имеют либо веса (2, 1), либо (2, 2), либо (3, 2). Таким об­ра­зом, срав­нив с мы од­но­знач­но вос­ста­но­вим веса всех четырёх монет. Среди них есть мо­не­та веса 2, будем срав­ни­вать с ней все осталь­ные мо­не­ты, на что уйдут остав­ши­е­ся взве­ши­ва­ния. Пер­вое утвер­жде­ние до­ка­за­но. Те­перь вы­ве­дем по ин­дук­ции сле­ду­ю­щее утвер­жде­ние, уси­ли­ва­ю­щее тре­бу­е­мое в за­да­че.

Утвер­жде­ние 2. Если есть k монет, среди ко­то­рых все три типа пред­став­ле­ны, то можно опре­де­лить, какая мо­не­та ка­ко­го типа, за k взве­ши­ва­ний.

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

Шаг. Срав­ним какие-ни­будь две мо­не­ты. Если они равны, то одну можно от­бро­сить (за­пом­нив, с какой она сов­па­да­ет по весу), и мы пе­ре­хо­дим к слу­чаю мо­не­ты, среди ко­то­рых все типы пред­став­ле­ны. Если они не равны, ска­жем что об­ра­зо­ва­лась пара и вос­поль­зу­ем­ся утвер­жде­ни­ем.

За­ме­ча­ние. Мы сде­ла­ли на одно взве­ши­ва­ние мень­ше, чем пред­по­ла­га­лось в усло­вии. Кроме того, мы ис­поль­зо­ва­ли толь­ко то, что сумма весов двух се­реб­ря­ных монет равна сумме весов мед­ной и зо­ло­той; тот факт, что се­реб­ря­ная мо­не­та вдвое тя­же­лее мед­ной, для дан­но­го ре­ше­ния не важен.

I спо­соб. Пер­вые три взве­ши­ва­ния такие: раз­би­ва­ем гири на две пары спо­со­бом, ко­то­рый ещё не встре­чал­ся, и срав­ни­ва­ем их. Раз­ных спо­со­бов как раз три. Мы по­лу­чим ра­вен­ство для пар 1001, 1005 и 1002, 1004. При этом толь­ко гиря 1001 в двух дру­гих взве­ши­ва­ни­ях была в «лёгкой» паре и толь­ко гиря 1005 в двух дру­гих взве­ши­ва­ни­ях была в «тяжёлой» паре  — так на­хо­дим их. Остав­ши­е­ся две гири 1002 и 1004 раз­ли­ча­ем четвёртым взве­ши­ва­ни­ем.

II спо­соб. Сна­ча­ла по­ло­жим на чаши по две гири.

1)  Одна из чаш пе­ре­ве­си­ла. Тогда гири раз­би­ва­ют­ся на две пары: лёгкую и тяжёлую. Есть два ва­ри­ан­та: лёгкая пара  — гири 1001, 1002, тя­же­лая  — 1004, 1005 или лёгкая пара  — 1001, 1004, тяжёлая  — 1002, 1005. Сле­ду­ю­щи­ми двумя взве­ши­ва­ни­я­ми упо­ря­до­чим гири по весу в каж­дой паре. Четвёртым взве­ши­ва­ни­ем, срав­нив более тя­же­лую гирю лёгкой пары с более лёгкой гирей тяжёлой пары, узна­ем, какой из ва­ри­ан­тов имеет место.

2)  Весы в рав­но­ве­сии. Тогда гири раз­би­ва­ют­ся на две пары рав­но­го веса: 1001, 1005 и 1002, 1004. Вто­рым и тре­тьим взве­ши­ва­ни­я­ми упо­ря­до­чим гири по весу в каж­дой паре. Четвёртым взве­ши­ва­ни­ем, срав­нив более лёгкие гири пар, узнаём, какая пара какая.

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

а) Как бы Таня ни по­ме­ща­ла гири на весы, рав­но­ве­сия они ни­ко­гда не по­ка­жут. По­это­му каж­дое взве­ши­ва­ние делит мно­же­ство по­до­зри­тель­ных пе­ре­ста­но­вок не более чем на две части. Вна­ча­ле было 24 по­до­зри­тель­ных пе­ре­ста­нов­ки, после пер­во­го взве­ши­ва­ния при «не­удач­ном» ис­хо­де их оста­нет­ся не мень­ше 12, после вто­ро­го  — не мень­ше 6, ..., после четвёртого  — не мень­ше 2.

б) I спо­соб. Сна­ча­ла по­ло­жим на чаши по две гири. В ре­зуль­та­те гири раз­би­ва­ют­ся на две пары: лёгкую и тяжёлую (если весы по­ка­за­ли рав­но­ве­сие, то, как мы знаем, более тяжёлая груп­па  — на левой чаше). Есть три ва­ри­ан­та: лёгкая пара  — гири 1000, 1002, тяжёлая  — 1004, 1005; лёгкая пара  — 1000, 1004, тяжёлая  — 1002, 1005; лёгкая пара  — 1000, 1005, тяжёлая  — 1002, 1004. Сле­ду­ю­щи­ми двумя взве­ши­ва­ни­я­ми упо­ря­до­чим гири по весу в каж­дой паре. Четвёртым взве­ши­ва­ни­ем срав­ним более тяжёлые гири обеих пар, по­ло­жив на левую чашу гирю из тяжёлой пары. В пер­вом ва­ри­ан­те пе­ре­ве­сит левая чаша, в тре­тьем  — пра­вая, а во вто­ром весы по­ка­жут рав­но­ве­сие (на левой чаша 1005, на пра­вой  — 1004).

II спо­соб. По­ло­жим гирю A на левую чашу, а гирю B  — на пра­вую. Если рав­но­ве­сия нет, более тяжёлую гирю кладём на левую чашу и вто­рым взве­ши­ва­ни­ем срав­ни­ва­ем с C. Если снова нет рав­но­ве­сия, опять более тяжёлую гирю кладём на левую чашу и тре­тьим взве­ши­ва­ни­ем срав­ни­ва­ем с D. У нас в за­па­се оста­лось одно взве­ши­ва­ние. Если рав­но­ве­сие хоть раз было, более тяжёлая гиря в этом взве­ши­ва­нии весит 1005 г, дру­гая  — 1004 г, а две остав­ши­е­ся гири опре­де­ля­ют­ся ещё одним взве­ши­ва­ни­ем. Если рав­но­ве­сия ни разу не было, мы за­ве­до­мо нашли самую тяжёлую гирю (1005 г). Раз­берём слу­чаи, какая это гиря, и по­ка­жем, что в каж­дом из них мы уже знаем также гирю 1004 г (тогда остав­ши­е­ся две гири мы раз­ли­чим четвёртым взве­ши­ва­ни­ем).

1)  Это A. Она все три взве­ши­ва­ния была на левой чаше, зна­чит, один раз весы по­ка­за­ли бы «рав­но­ве­сие», а этот слу­чай разо­бран.

2)  Это B. Она два­жды была на левой чаше, по­это­му 1004 г может ве­сить толь­ко A.

3)  Это C. Тогда 1004 г весит гиря, «про­иг­рав­шая» C при вто­ром взве­ши­ва­нии (так как она более тяжёлая из A и B, а D не может ве­сить 1004 г).

4)  Это D. Тогда 1004 г весит самая тяжёлая гиря из трёх остав­ших­ся (она опре­де­ли­лась при вто­ром взве­ши­ва­нии).

Ответ: а) не может; б) может.