Олимпиадные задачи по математике для 10-11 класса - сложность 2-3 с решениями

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

В стране 1988 городов и 4000 дорог.

Докажите, что можно указать кольцевой маршрут, проходящий не более, чем через 20 городов (каждая дорога соединяет два города).