Богданов И.И. — олимпиадные задачи по математике - сложность 4 с решениями

Даны натуральные числа <i>a</i> и <i>b</i>, причём  <i>a < b</i> < 2<i>a</i>. На клетчатой плоскости отмечены некоторые клетки так, что в каждом клетчатом прямоугольнике <i>a</i>×<i>b</i> или <i>b</i>×<i>a</i> есть хотя бы одна отмеченная клетка. При каком наибольшем α можно утверждать, что для любого натурального <i>N</i> найдётся клетчатый квадрат <i>N</i>×<i>N</i>, в котором отмечено хотя бы α<i>N</i>² клеток?

У нумизмата есть 100 одинаковых по внешнему виду монет. Он знает, что среди них 30 настоящих и 70 фальшивых монет. Кроме того, он знает, что массы всех настоящих монет одинаковы, а массы всех фальшивых – разные, причём каждая фальшивая монета тяжелее настоящей; однако точные массы монет неизвестны. Имеются двухчашечные весы без гирь, на которых можно за одно взвешивание сравнить массы двух групп, состоящих из одинакового числа монет. За какое наименьшее количество взвешиваний на этих весах нумизмат сможет гарантированно найти хотя бы одну настоящую монету?

Паутина имеет вид клетчатой сетки 100×100 узлов (другими словами, это сетка 99×99 клеток). В каком-то её углу сидит паук, а в некоторых 100 узлах к паутине приклеились мухи. За ход паук может переместиться в любой соседний с ним узел. Может ли паук гарантированно съесть всех мух, затратив не более

  а) 2100 ходов;

  б) 2000 ходов?

В государстве <i>n</i> городов, и между каждыми двумя из них курсирует экспресс (в обе стороны). Для каждого экспресса цены билетов "туда" и "обратно" равны, а для разных экспрессов эти цены различны. Докажите, что путешественник может выбрать начальный город, выехать из него и проехать последовательно на  <i>n</i> – 1  экспрессах, платя за проезд на каждом следующем меньше, чем за проезд на предыдущем. (Путешественник может попадать несколько раз в один и тот же город.)

На каждой из 2013 карточек написано по числу, все эти 2013 чисел различны. Карточки перевёрнуты числами вниз. За один ход разрешается указать на десять карточек, и в ответ сообщат одно из чисел, написанных на них (неизвестно, какое).

Для какого наибольшего <i>t</i> гарантированно удастся найти <i>t</i> карточек, про которые известно, какое число написано на каждой из них?