For several years now, the Nordic Conference on Partitions and Combinatorics, NCPC, has had a growing number of participants.
This year the organizing team is expecting an all time high record in the hundreds. Due to the politics of arranging this prestigious event, the conference site was decided a long time ago to be the Grand H^otel in Stockholm. The hotel has two large dining halls, but unfortunately, each of these halls alone can only fit up to two thirds of the NCPC participants, so the participants are going to have to be divided in two groups.
This constraint calls for some thinking on behalf of the organizing team for the conference dinner: could they come up with some division of the participants in two parts, none of which is larger than 2/3 of the entire group, meeting some witty division rule suitable for the occasion, which they could tell the participants for their amusement? After all, as long as there is some grand logic rule to which of the two dining halls you are being seated in, you (as a mathematician) would be happy! They thought for a while and came up with the following idea for the division: Is there a year Y and a division of the participants in two parts such that every pair in the first part met for the first time some time before year Y , and every pair in the second part met for the first time some time in or after year Y ? Now this clearly qualified as an appropriate rule to all of them, but the question was whether it would be possible?
입력 4 6 1 2 1987 2 3 1987 1 3 1987 2 4 1987 1 4 1987 3 4 1987 출력 Impossible 입력 6 3 1 2 1970 3 4 1980 5 6 1990 출력 1971
출처:ncpc/2008/Problem D