Browse · MathNet
PrintEstonian Mathematical Olympiad
Estonia counting and probability
Problem
The website of a company has multiple pages, which may point to each other. A list containing each of these pages exactly once is called natural, if whenever one page points to another, it is written before the other page. The webmaster of the company has a natural list of pages. Then she reorders the pages, writing down first all pages which are not pointed to by any other page, then all pages which the first page of the original list points to, then all pages which the second page of the original list points to and which are not listed yet etc.
a. It is known that each page is pointed to by at most one other page. Can we be certain that the new list is natural?
b. It is not known whether each page is pointed to by at most one other page. Can we be certain that at least one possible new list is natural?
a. It is known that each page is pointed to by at most one other page. Can we be certain that the new list is natural?
b. It is not known whether each page is pointed to by at most one other page. Can we be certain that at least one possible new list is natural?
Solution
We write whenever the page points to the page .
a. Consider any two pages and with . By the assumption, is not pointed to by any other page. Thus is located in the new list in the group of pages pointed to by page . We consider two cases. If is not pointed to by any page, then it is in the first group, and thus also before . If is pointed to by a page , then is in the group of pages pointed to by . But as the initial list is natural, must be before in it. Thus in the new list, must be before .
In either case, is before in the new list, making it natural, as desired.
Fig. 8
b. Let there be 4 pages with , , and (Fig. 8). Then the list is natural. The new list can then be either or . But neither of them is natural, as the last page points to the page before it.
a. Consider any two pages and with . By the assumption, is not pointed to by any other page. Thus is located in the new list in the group of pages pointed to by page . We consider two cases. If is not pointed to by any page, then it is in the first group, and thus also before . If is pointed to by a page , then is in the group of pages pointed to by . But as the initial list is natural, must be before in it. Thus in the new list, must be before .
In either case, is before in the new list, making it natural, as desired.
Fig. 8
b. Let there be 4 pages with , , and (Fig. 8). Then the list is natural. The new list can then be either or . But neither of them is natural, as the last page points to the page before it.
Final answer
a. Yes. b. No.
Techniques
Graph TheoryAlgorithms