Как элементарная задача о голубях способствует развитию теории сложности в математике
Когда голубей становится больше, чем гнёзд, некоторым птицам приходится ютиться вдвоём. У этого очевидного утверждения — и его обратной стороны — есть глубокие связи со многими областями математики и информатики. Американцы говорят, что птица в руке стоит двух в кустах, но для компьютерных учёных две птицы в гнезде ещё лучше. А всё потому, что эти...






