At the faculty of mathematics study $40$ boys and $10$ girls. Every girl acquaintance with all boys, who older than her, or tall(higher) than her. Prove that there exist two boys such that the sets of acquainted-girls of the boys are same.
Problem
Source:
Tags: combinatorics proposed, combinatorics
R8450932
12.02.2018 18:52
Any solution? Generally what ideas can be used in this kind of problems? Does anyone know similar problems?
Bad_Math
12.02.2018 22:53
This seems like a Dirichlet's (Pigeonhole) Principle problem. We might be able to prove that there can only exist 39 boys so that each of their girl-sets is different, so two of them must have the same one. If you just google I am sure you can find problems on this.
R8450932
12.02.2018 23:26
Bad_Math wrote:
This seems like a Dirichlet's (Pigeonhole) Principle problem. We might be able to prove that there can only exist 39 boys so that each of their girl-sets is different, so two of them must have the same one. If you just google I am sure you can find problems on this.
Hmm İ am not sure how it works ad I would not say Pigeonhole easily destroys Russian problem
ColaTurka_2
26.06.2018 06:05
I tried Pigeonhole on the problem. Supposedly we have to ensure that there is less than 40 boxes there. But I got 56 boxes if the girls is set ascending in age but descended in the order of height.
akhan98
20.01.2022 11:35
Consider girls with tallness x, age y on 2d coordinate plane. Then if she is friend with everyone taller, that is all boys in the right half plane from her (let's say there are k of those girls). Similarly if she is friend with everyone older than her it is upper half of the plane (l of those girls). So we have k vertical and l horizontal lines dividing our plane into (k + 1) * (l + 1) regions, given l + k = 10, maximum value is 36 regions. Thus two guys will fall into the same region, which will ensure they are friends with the same set of girls.