Международный научно-образовательный электронный журнал «образование и наука в XXI веке». Выпуск №10 (том 1)

 
 
 
 
13. В классе 26 учеников, из них более половины мальчики. Докажите, что какие-то два 
мальчика сидят за одним столом, если в классе 13 столов. 
Решение. Пусть мальчики – «зайцы», а столы – «клетки». Т.к. мальчиков больше половины, 
т.е. больше 13 – числа столов, то по принципу Дирихле найдется стол, за которым сидят не 
менее двух мальчиков. А т.к. больше двух мальчиков за стол не помещается, то это означает, 
что найдется стол, за которым сидят два мальчика. 
14. В ковре размером 3х3 м. Коля проделал 8 дырок. Докажите, что из него можно вырезать 
коврик размером 1х1, не содержащий внутри себя дырок ( дырки можно считать точечными). 
В данной задаче для решения необходимо применить другую формулировку принципа 
Дирихле. Пусть в n клетках сидит m зайцев, причем n больше m. Тогда 
найдется хотя бы одна пустая клетка. Здесь дырки будут 
«зайцами».Разрежем ковер на 9 ковриков размером 1х1 м.. Т.к. ковриков - 
«клеток» - 9, а дырок – «зайцев» - 8, то найдется хотя бы одна «клетка», в 
которой не будет «зайцев», т.е. найдется коврик без дырок внутри.
Таким образом, применяя данный метод, надо: 
1.
Определить, что удобно в задаче принять за «клетки», а что – за 
«зайцев». 
2.
Получить «клетки». Чаще всего «клеток меньше (больше), чем 
«зайцев» на одну 
( или более). 
3.
Выбрать для решения требуемую формулировку принципа Дирихле. 
 
4. Инвариант и раскраски. 
Эта лекция посвящена одному, но очень важному математическому понятию- инварианту. 
1 
2 
3 
3 
1 
2 
2 
3 
1 

---

107 
Бывает он в задачах, где мы имеем дело с какими-то операциями, с каким-то процессом, который 
изменяет данный в условии объект. Вот если у объекта есть какое-то свойство или 
характеристика, которая 
не меняется 
при этих операциях - она и называется 
инвариантом. 
Если 
у объекта есть два состояния, при которых инвариант принимает 
разные значения, 
то из одного 
из них 
нельзя перейти 
в другое (и из второго в первое тоже). Но одинаковое значение инварианта 
еще не значит, 
что так перейти можно.
Четность, рассмотренная нами в одной из предыдущих лекций - типичный пример
инварианта.
Задача 1.
В файле хранятся 2003 единицы и 232 нуля. Программа читает из файла два
произвольных числа, стирает, и записывает на их место О, если они были равны, и 1, если
нет. Программа запускается многократно. В конце в файле остается только одно число.
Чему оно равно, О или 1?
Решение:
Несмотря на то, что вариантов действия программы очень много, мы можемустановить 
ответ однозначно. Что может прочитать программа за каждый отдельный запуск? Либо О и О (и 
записать О),
либо О и 1 (и записать 1), либо 1 и 1 (и записать О). В первых двух случаях 
сумма всех чисел 
в файле 
не меняется, 
в последнем - уменьшается на 2. В любом случае, 
четность 
этой суммы 
остается 
прежней. 
Исходно сумма была 2003* 1+232*0=2003 - нечетная, значит, 
и в конце 
будет нечетная. 
Но в конце 
остается только одно число - оно и равно сумме всех - поэтому 
оно нечетное 
. А так как в файле
бывают только нули и единицы, то это 1.