В деревне Гадюкино у каждого мальчика все знакомые девочки знакомы между собой. А у каждой девочки среди ее знакомых мальчиков больше, чем девочек. Докажите, что в деревне Гадюкино мальчиков не меньше, чем девочек.
Каждая девочка знакома со всеми остальными девочками. значит девочковое население деревни это все ее знакомые девочки плюс она сама. знакомых мальчиков у каждой девочки большеминимум на одного, значит мальчиков или столько-же, сколько девочек, или больше.
Админ: "Каждая девочка знакома со всеми остальными девочками" - совсем не обязательно.
Вася Пупкин 2011-09-08 08:09:45 пишет:
Предположим, девочки решили повязать мальчиков. Для этого они рассчитались по номерам, и поехали по очереди. Кждая девочка, когда до нее доходит очередь, выбирает из свих знакомых мальчиков незанятого, и всем его знакомым девочкам сообщает "этот мальчик занят, отвали". Может ли так случиться, что какой-то девочке, когда до нее дойдет очередь, будет не из чего выбирать, то бишь, все ее знакомые мальчики уже заняты? "Это мой, отвали" она может услышать о каждом мальчике только один раз, и только от знакомой, и только от знакомой через этого мальчика. То бишь, в своем списке знакомых мальчиков она вычеркивает занятых, ставя против каждого имя занявшей его девочки(ее знакомой). Но в самом худшем случае ее знакомые девочки отрежут ей не больше знакомых мальчиков, чем их, знакомых девочек, количество. А по условию, у каждой девочки знакомых мальчиков больше, чем знакомых девочек. Следовательно, любая девочка сможет застолбить мальчика, следовательно, мальчиков не меньше. Мы ничего не говорили при этом о девочках, у которых накомых мальчиков вовсе нет -- но таких девочек, по условию, тоже не существует(даже с нулевым количеством знакомых девочек ей придется иметь хоть одного знакомого мальчика) -- то бишь, в процессе таки действительно всех девочек перебрали(а мальчики, кстати, вполне еще могли остаться и ни с кем не знакомые одиночки, не вовлеченные).
1) все знакомые девочки мальчика знакомы между собой => они друг друга знают
2) количество знакомых мальчиков у девочки больше чем знакомых девочек => мальчиков больше