Logic+ 06
Problem A
There are 5 towns.
Some of them are connected by direct roads, that is by roads not going through other towns.
It's known that among any group of 4 towns out of these 5 there is always one town connected by direct roads with each of the other 3 towns of this group.
Prove that there is at least one town connected with all 4 others by direct roads.
Proof A
Choose any 4 towns from given 5 as the first group towns.
One of these towns is connected to 3 others, as the problem states. Let's call this town A and the others will be B, C and D.
Let's use the term connector to describe a town in a group that is connected by direct roads to all other towns in the same group.
So, A is a connector in the first group.
The fifth town that is not in this group will be called E.
So far, the following roads are established: AB, AC and AD.
Now consider the second group of 4 towns {B, C, D, E}.
As you see, we eliminated from the first group town A that had roads to other 3 towns of this group and added town E which was not in it.
One of the towns in this second group should be connected by direct roads with each other 3 towns, as the problem states.
Here we have different cases, which we consider separately.
Case A1
If B, C or D is the town connected to all 3 others in this second group, then this is the town connected to all 4 other towns since it is also connected to A, as we know from the analysis of the first group.
Here is the road map if B is the town in this group that is connected to all others.
Analogous situation would be if C or D are connected to 3 other towns in this group.
This is the logical end of a proof for this case.
Case A2
If E is the town connected to 3 others by direct road, the list of roads is expended by adding the following roads: EB, EC and ED.
Now the roads map looks like this
Consider the next group of 4 towns: A, B, C and E.
One of the towns in this third group should be connected by direct roads with each other 3 towns, as the problem states.
Case A2.1
If A or E is connected to all other towns in this third group, it implies the existence of a road AE and A is the town connected to all 4 other towns. This is the logical end of a proof in this case.
Case A2.2
If B or C is connected to all other 3 towns in this third group, it means including a road BC into our map
In this case consider the fourth group A, C, D and E.
If A or E are the towns with three connections, we have to add road AE, and each one of them would be connected to all other 4 towns.
If we chose to connect C and D for the same purpose, then C will be connected to all other 4 towns.
In any case, the condition that in each group of 4 out of 5 towns there is one town connected by a direct road to 3 others is sufficient for existing of one town connected by direct roads to all other 4 towns.
End of Proof.
Problem B
(continuation of Problem A)
There are 6 towns.
Some of them are connected by direct roads, that is by roads not going through other towns.
It's known that among any group of 4 towns out of these 6 there is always one town connected by direct roads with each of the other 3 towns of this group.
Prove that there is at least one town connected with all 5 others by direct roads.
Proof B
Choose any 5 towns from 6 as the first group.
According to Problem A, there must be at least one town in this group connected to 4 others. Let's call this town A and the others will be B, C, D and E.
The sixth town that is not in this group will be called F.
So far, the following roads are established: AB, AC, AD and AE.
Our second group of 5 towns excludes A and includes F.
As before, according to Problem A, it must have a town connected to other 4 towns in this second group.
If this one town is one of those that participated in the first group, that is B, C, D or E, the problem is solved because this town also was connected to A and, therefore, we found a town connected to all 5 other towns.
Assume, it's town F that connected to other 4 towns of the second group.
This necessitates adding to our map the roads FB, FC, FD and FE.
Our third group includes towns B, C, D and E.
One of this group of 4 towns must be connected to 3 others. But any of these 4 towns is connected to A and F, which makes it connected to all 6 towns.
End of proof.
Problem C
(continuation of Problem B using a method of induction)
There are N+1 towns.
Some of them are connected by direct roads, that is by roads not going through other towns.
It's known that among any group of 4 towns out of these N+1 there is always one town connected by direct roads with each of the other 3 towns of this group.
Assume that it's also known that among any group of K towns out of these N+1, where K is less or equal to N, there is always one town connected by direct roads with each of the other K−1 towns of this group.
Prove that there is at least one town connected with all N others by direct roads.
Hint C: Follow the logic of a proof in Problem B.
No comments:
Post a Comment