*Notes to a video lecture on http://www.unizor.com*

__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**out of these

*4*towns*5*

**there is always one town connected by direct roads with each of the other**of this group.

*3*townsProve 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

*and the others will be*

**A***,*

**B***and*

**C***.*

**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,

*is a*

**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***and*

**AC***.*

**AD**Now consider the second group of

*4*towns {

*}.*

**B, C, D, E**As you see, we eliminated from the first group town

*that had roads to other*

**A***3*towns of this group and added town

*which was not in it.*

**E**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***or*

**C***is the town connected to all*

**D***3*others in this second group, then this is the town connected to all

*4*other towns since it is also connected to

*, as we know from the analysis of the first group.*

**A**Here is the road map if

*is the town in this group that is connected to all others.*

**B**Analogous situation would be if

*or*

**C***are connected to*

**D***3*other towns in this group.

This is the logical end of a proof for this case.

*Case A2*

If

*is the town connected to*

**E***3*others by direct road, the list of roads is expended by adding the following roads:

*,*

**EB***and*

**EC***.*

**ED**Now the roads map looks like this

Consider the next group of

*4*towns:

*,*

**A***,*

**B***and*

**C***.*

**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

*or*

**A***is connected to all other towns in this third group, it implies the existence of a road*

**E***and*

**AE***is the town connected to all*

**A***4*other towns. This is the logical end of a proof in this case.

*Case A2.2*

If

*or*

**B***is connected to all other*

**C***3*towns in this third group, it means including a road

*into our map*

**BC**In this case consider the fourth group

*,*

**A***,*

**C***and*

**D***.*

**E**If

*or*

**A***are the towns with three connections, we have to add road*

**E***, and each one of them would be connected to all other*

**AE***4*towns.

If we chose to connect

*and*

**C***for the same purpose, then*

**D***will be connected to all other*

**C***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**out of these

*4*towns*6*

**there is always one town connected by direct roads with each of the other**of this group.

*3*townsProve 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

*and the others will be*

**A***,*

**B***,*

**C***and*

**D***.*

**E**The sixth town that is not in this group will be called

*.*

**F**So far, the following roads are established:

*,*

**AB***,*

**AC***and*

**AD***.*

**AE**Our second group of

*5*towns excludes

*and includes*

**A***.*

**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***or*

**D***, the problem is solved because this town also was connected to*

**E***and, therefore, we found a town connected to all*

**A***5*other towns.

Assume, it's town

*that connected to other*

**F***4*towns of the second group.

This necessitates adding to our map the roads

*,*

**FB***,*

**FC***and*

**FD***.*

**FE**Our third group includes towns

*,*

**B***,*

**C***and*

**D***.*

**E**One of this group of

*4*towns must be connected to

*3*others. But any of these

*4*towns is connected to

*and*

**A***, which makes it connected to all*

**F***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**out of these

*4*towns*N+1*

**there is always one town connected by direct roads with each of the other**of this group.

*3*townsAssume that it's also known that among

**any group of**out of these

*K*towns*N+1*, where

*is less or equal to*

**K***,*

**N****there is always one town connected by direct roads with each of the other**of this group.

*K−1*townsProve that there is

**at least one**town connected with all

*others by direct roads.*

**N***Hint C*: Follow the logic of a proof in

*Problem B*.

## No comments:

Post a Comment