Proving Mutual Unknowns in a Room: Hamiltonian Walks

[squaremeplz]

Homework Statement

There are (m-1)n+1 people in the room. Show that there are at least n people who mutually do not know each other, or there is a person who knows at least n people

Homework Equations

The Attempt at a Solution

I think this has to do with hamiltonian walks.

The formula expands to

m*n + m - n - 1 = x

if m and n are both even integers with, m = n or distinct then the result is always odd

if m and n are both odd integers with, m = n or distinct then the result is always even

if m is an odd integer and n is even then, or vice versa, the result is even

does this have to do with x being the number of edges?

or do m and n stand for nodes, edges or vice versa?

is this related to a hamiltonian cycle?

lets say the total number of people x is even. then there is a hamiltonian walk and one person, knows at least n people.

if the number is odd, then there is no closed walk because more than two nodes would have odd edges.

 

[mighty2000]

Hi there, you are correct in thinking that this problem involves Hamiltonian walks. Let's break it down step by step to understand why this is the case.

First, let's define m and n as the number of people in the room and the number of connections between them, respectively. This means that the total number of people in the room is (m-1)n+1, as stated in the problem.

Next, let's consider the extreme cases. If m = 1, then there is only 1 person in the room and there are no connections between them. In this case, there is clearly a person who knows at least n people, since there is only one person in the room.

On the other hand, if m = n, then there are n people in the room and each person is connected to every other person. In this case, there is a mutual connection between every pair of people, meaning that there are no people who do not know each other.

Now, let's consider all the other cases where m is not equal to 1 or n. In these cases, there must be at least one person who knows more than one other person. This is because if every person knows only one other person, then the maximum number of connections possible is n, which is equal to the number of people in the room. This means that there is no person who knows at least n people, and therefore there must be at least one person who knows more than one other person.

Now, let's look at the number of connections between these people who know more than one other person. It is clear that this number must be less than or equal to (m-1)n, since there are (m-1)n connections between m people. This means that there must be at least one person who knows at least n other people, since otherwise there would be more than (m-1)n connections, which is not possible.

Therefore, we have shown that in all cases where m is not equal to 1 or n, there is either a person who knows at least n people, or there are n people who do not know each other. This is because if there is no person who knows at least n people, then there must be at least one person who knows more than one other person, and therefore there must be at least n people who do not know each other.

I hope this helps to clarify the solution to this problem. Keep up