Городская Жаутыковская олимпиада, 9 класс, 2002 год

В клетчатом квадрате $19\times 19$ закрашено 95 клеток. Докажите, что найдется прямоугольник $3\times 5$, в котором закрашено не более трех клеток. Покажите, что можно так закрасить 96 клеток, что в каждом прямоугольнике $3\times 5$ будет закрашено не менее четырех клеток.