Imagine you are at the social get-together with at most 500 guests. The host invites you all to have dinner. There are several tables in the dining room. The way the guests sit down at the tables is the following: each one sitting not alone at a certain table must know at least one person sitting at the same table and no one else sitting at other tables.
It is supposed that if a person knows a second person, the second one knows the first person too. No one introduces himself to the other persons sitting at the same table. That means that if two persons are sitting at the same table, but initially they do not know each other, they will not know each other afterwards either.
|Determine how many tables are
necessary and the persons sitting at each table (20 points). At each table there is only
one person who will talk to the waiter; he/she is called the leader of the table. Each
person relays his wishes concerning the menu to the persons he knows. The time allocated
to each person to relay his wishes to each person he knows is supposed to be the same for
|Determine the most suitable
person as leader of the table in order to receive information from all the persons sitting
at the table in the shortest possible period of time; produce at output the leader of each
table and the corresponding period of time(20 points). Afterwards, the host wishes to
unify tables. For this purpose, he calls some friends. Each of them, when coming, is
introduced to the leaders of two tables, links the tables, sits down at the new formed
table and becomes the leader of this table.
|What is the order of linking
the tables in this way, so that at last all tables unified into a single one and the
conditions of the previous point are satisfied? Specify the minimum necessary period of
time for the leader to get information from all the other persons. (30 points)
After the complete linking, the friends of the host are leaving and the tables get their initial structure until the end of the dinner. When the dinner is over, the persons start leaving the tables.
|Determine, for each table, the
minimum number of persons and the order in which they are leaving the table, until the
persons who are still at the table do not know each other. (30 points)
Suppose the number of persons is 8 and: