Lift Problem

Originally posted by itisi
A lift contains 6 people. Prove that either at least 3 people know each other or at least 3 people don't know each other.
(Assume that if A knows B, B knows A.)

---
HINT: Draw a graph.

it's a 1 story building and the lift (elevator) goes from the basment to the 1st floor. The building contains only one company. Therefore everyone on the lift knows each other. Otherwise they wouldn't be in the elevator.

No graph needed.

Originally posted by itisi
A lift contains 6 people. Prove that either at least 3 people know each other or at least 3 people don't know each other.
(Assume that if A knows B, B knows A.)

---
HINT: Draw a graph.

There are 6 people, if 3 or more people know each other you've fulfilled the requirement that 3 people know each other and if 3 or fewer people know each other then you've fulfilled case that at least 3 people don't. This covers all possibilities.

Originally posted by DeepThought
There are 6 people, if 3 or more people know each other you've fulfilled the requirement that 3 people know each other and if 3 or fewer people know each other then you've fulfilled case that at least 3 people don't. This covers all possibilities.

No; in a subgroup of three people (A, B, and C) it might be that A knows B, and B knows C, but A doen't know C. So neither case is fulfilled.

Originally posted by GregM
No; in a subgroup of three people (A, B, and C) it might be that A knows B, and B knows C, but A doen't know C. So neither case is fulfilled.

What are we meant to be counting then? If you are counting pairs of people who know each other then if everyone knows everyone else thats 15 pairs of people who know each other, in which case your conditions will be automatically fulfilled (A graph containing 6 points all of which are linked has 15 links, colour the links red or green. Either the number of red links is 3 or more or it isn't in which case the number of green links is greater than 12). I doubt this is what you have in mind, so it's not really clear what you mean by the number of people who know each other given that you've rejected my other answer.

Edit: Are you asking us to prove that either there has be a subset with three people in all of whom know each other or a subset with three people none of whom know each other?

Originally posted by itisi
A lift contains 6 people. Prove that either at least 3 people know each other or at least 3 people don't know each other.
(Assume that if A knows B, B knows A.)

---
HINT: Draw a graph.

Represet the people by dots, connect dots if the people know eachother.

Suppose there is no group of three people that know eachother (meaning that there are no triangles in your figure). Below are all possibilities that can occur in your figure with a group of three people that don't know eachother behind it (with the appropiate names).

Loop ABCDEFA --> ACE
Loop ABCDEA, single F --> ACF
Loop ABCDA, single E, F --> ACE
Loop ABCDA, line EF --> ACE
Line ABCDEF --> ACE
Line ABCDE, single F --> ACE
Line ABCD, single E, F --> ACE
Line ABCD, EF --> ACE
Line ABC, single D, E, F --> ACD
Line ABC, DE, single F --> ACD
Line ABC, DEF --> ACD
Line AB, single C, D, E, F --> ACD
Line AB, CD, single E, F --> ACE
Line AB, CD, EF --> ACE

Originally posted by TheMaster37
Represet the people by dots, connect dots if the people know eachother.

Suppose there is no group of three people that know eachother (meaning that there are no triangles in your figure). Below are all possibilities that can occur in your figure with a group of three people that don't know eachother behind it (with the appropiate names).

Loop ABCD ...[text shortened]... --> ACD
Line AB, CD, single E, F --> ACE
Line AB, CD, EF --> ACE

I think you also have to consider trees: ABCD linked to CEF (ACF is an unlinked triangle) or ABCD and BE and CF (BDF) as well as loops with trees coming off them: eg. ABCDEA and EF (BDF), ABCDA and BE and DF (CEF), and ABCA and AD and BE and CF (DEF), or ABCA and AE and AF (BEF). And some double loops ABCDA linked to AEC (BDE) or ABCDA linked to AEFC (BDE). Each of these cases, and I haven't exhausted them, has the required peoperty that there are no triangles - and also has the property that there are 3 points not directly linked.

Originally posted by itisi
Impressed with proofs offered so far. Graphically, with a hexagon whose vertices represent the people (A to F), we can use lines of two colours to represent knowing or not knowing. Hence, a triangle of one colour proves the original statement, but we will try as hard as possible not to make one.

1. There must be at least three lines of one colour (X) from D). If it is colour (Y), there is a triangle (BCD).

QED (I think this is the nicest proof.)

Problem is it doesn't work. If it did then you would only need 4 people in the lift to fulfil the conditions. Call them ABC and D - Consider the loop ABCDA. By cyclic symetry one subset is as good as any of the others. Let's pick ABC, not all of them know each other (A doesn't know C) and not all of them are unknown to each other (A knows B). Basically you can't have proposition 1 and exhaust all possible cases. What you have done is the part of the proof for A(3) from luskin's proof.

I think that luskin's proof is the only one that works fully. It can be improved slightly, A(2) implies A(1) and A(0) (essentially you have A not knowing D, E, F and whether or not A knows B and C you get the contradiction) similarly the proof for A(3) automatically proves A(4) and A(5). It is also far more elegant than my method below, but once I'd worked it out I decided I may as well post it. The Master37's proof almost works, except he's missed out some cases.

To complete Master37's proof I'm going to introduce some language. Each person corresponds to a vertex, vertices are linked if the corresponding people know each other otherwise they are unlinked. A vertex is of order 0 if it is isolated, of order 1 if the corresponding person knows only one other person and so on. If vertices are linked they are neighbouring, otherwise they are non-neighbouring. We are trying to prove there are always three vertices all of whom are neighbouring or all of whom are non-neighbouring. A path is the vertices you have to pass to get from one vertex in the graph each step of which has to be between linked vertices.

Now we need to classify the types of graph we can get which don't contain loops of length 3 which I'll sometimes refer to as triangles. Graphs can either be disjoint or connected. There can be upto 6 subgraphs (all vertices of order 0).

To make progress we need to classify the types of graph. There are the following types of subgraph:

Isolated vertex.
Chains: two vertices of order 1 and the rest of order 2.
Trees: At least 1 vertex of order 3, no closed loops (ie there is only one path between any two vertices in the graph).
Simple loops: All vertices in the graph are of order 2, there are exactly 2 paths between any two points, loops of length 2 are ruled out (A knows B already implies B knows A) as are loops of length 1 (A knows A is trivial).
tadpoles: A simple loop with 1 or more chains coming off it. The chains can be connected at the same or different vertices.
non-simple loops: a graph where all the vertices have order greater than 1 and there are more than two paths between vertices.
non-simple tadpoles: chains connected to non-simple loops.

Tadpoles with 2 heads can't happen with less than 7 vertices, and then they have 2 triangles seperated by a link.

First consider disjoint graphs. If there are three or more subgraphs in a disjoint graph then we simply choose one vertex from three different subgraphs and have found three points that are non-neighbouring. This leaves graphs with 2 subgraphs. Pick a point from the smaller subgraph, if the subgraphs are the same size pick a point from either subgraph. We are then looking for two non-neighbouring vertices in the other sub-graph. If a graph has more than two vertices and has no non-neighbouring vertices then it has 3 or more neighbouring vertices. This is the same argument as luskin's proof for A(0), A(1) and A(2). So all disjoint graphs have either 3 neighbouring or 3 non-neighbouring vertices.

So we now only need to consider connected graphs. A connected graph contains all 6 vertices, for a chain of length 6 we can choose alternate vertices as we can for a simple loop, trees have 3 or more vertices of order 1 and those are non-neighbouring (otherwise the graph wouldn't contain all the vertices). Tadpoles have a loop connected to one or two tails. If there is one tail we can pick the endpoint of the tail and the two vertices neighbouring the one that attaches the tail, if those two are neighbouring then as they both also neighbour the tail connector there are three vertices that are neighbouring, if not then those two vertices and the tail's endpoint are non-neighbouring. If there are two tails then we can choose the two vertices of order 1 and one of the two vertices from the loop which is of order 2 (the loop has to be simple since it is of length 4, if it is not we'll have a loop of length 3) these will all be non-neighbouring.

This leaves non-simple loops. We can make a non-simple loop from a simple one by starting with a subgraph which is a simple loop of length 4, 5 or 6 and then linking any missing vertices in. Start with a simple loop of length 6, we can only add links. Pick a set of three non-neighbouring vertices they are all seperated by one vertex. There is no point in adding a link between neighbouring vertices, if they are seperated by only 1 vertex you get a loop of length 3, so the only non-trivial case is when the vertices we are linking are 3 steps away from one another. We can add up to three links in this way. This construction has not linked any of the original set of non-neighbouring vertices to each other, so they remain non-neighbouring.

Now we can move onto the case where we start with a loop of length 5, any pair of vertices on the pentagon are either neighbouring, or there is a path of length 2 between them. Note that this means that adding a link of length 1 then will give us a loop of length 3. We want to find a way of connecting the final vertex which doesn't generate loops of length 3. Pick 2 vertices on the pentagon, if they are neighbouring then we will get a loop of length 3, if they are not neighbouring then they can be no further than 2 steps away from one another. Connect the missing vertex to these two vertices. There are now three paths between these two vertices, each with at least one vertex in, picking one vertex from each path gives us three non-neighbouring vertices. Adding further links to the original vertices will generate a loop of length 3 as we saw earlier, adding a link from the new vertex to any of the other vertices of order 2 generates a triangle since the new vertex neighbours both the vertices of order 3 at least one of which neighbours the vertex linked to.

Finally we have non-simple loops made from loops of length 4. As with the pentagon adding a link of length 1 to any non-neighbouring vertices generates a triangle. There are two possible ways of linking in the two other vertices, seperately or together (ie add a link of length 3). If we add them in together we can connect them to two neighbouring vertices, this is the same as the loops of length 6 starting point above so we have already covered it. The alternative was to link them to a pair of non-neigbouring vertices. We already know that adding a link to the original vertices generates a triangle, adding a link between one of the new vertices and one of the original vertices gives us a loop of length 3 since the new vertex neighbours one of the vertices of order 3 on one side which neighbours the two vertices of order 2, and it shares a neighbour with the other vertex of order 3.

This leaves adding in two links of length 2. Since we are adding links of length 2 they cannot be added to neighbouring vertices. So adding the first is unique. The second can be added in three ways. 1) To the same vertices as the first one, 2) To the other pair of vertices from the original figure, and 3) between the new vertex and one of the two vertices of still of order 2 from the original figure.

1) Adding further links generates triangles since all the vertices of order 2 neighbour both vertices of order 4, and the vertices of order 4 share all their neighbours. There are 4 vertices of order 2 and they are non-neighbouring.

2) There is one and only one way of adding an extra link of length 1. The two new vertices do not share any neighbours so they can be linked. Pick one of the new vertices, it does not neighbour the two neighbours of the other new vertex. This is unchanged by adding the link of length 1.

3) All the vertices either neighbour, or share a neighbour with all the others so no links of length 1 can be added. The vertex connected does not neighbour the two vertices of the original square it was not connected to which also do not neighbour each other.

There are no other cases which do not contain triangles. I've therefore shown that either the graph contains triangles or it does not, but if not must then have 3 non-neighbouring points, which confirms the conjecture.

Originally posted by DeepThought
[b]Problem is it doesn't work. If it did then you would only need 4 people in the lift to fulfil the conditions.

The method given by itisi may be sound. In the case of 4 people in the lift there need only be two lines of the same colour starting from A, and the graph could be made to disprove.

Originally posted by itisi
DeepThought, I don't see how my logic doesn't prove the original hypothesis.

It does, my mistake - I misread 1.