Santas at Christmas party

[pruse]

peterruse: Your method and equation are correct, but the solution is n=100 not 56.

Still, the real question is whether such a Xmas party is mathematically consistent.

I appreciate the Xmas spirit, but its easier to talk about graphs: each Santa is a node and a pair of Santas are friends if they are connected by an edge.

Let (k,\ell >0) be integers. Let (G(k.\ell)) be a graph such that

1) every node is attached to exactly (k) edges,
2) if two nodes (a) and (b) are both attached to some node (v), then (a) and (b) are not connected,
3) if two nodes are not connected, then there are exactly (\ell) common nodes that they are both connected to,

if such a graph exists. For example, the Santa party is the graph (G(k,\ell)) with (k=22) and (\ell=6).

Then (G(k,\ell)) has (1+k+\frac{k(k-1)}\ell) nodes. This can be proved using peterruse's method, but there is a simpler way: Fix a node (v). Let (A) be the set of nodes connected to (v). Hence (|A|=k), i.e. (A) has (k) nodes. Then let (B) be the remaining nodes which are not connected to (v) (and not including (v)). Then each (a\in A) is connnected to (k-1) nodes in (B). Therefore there are (k(k-1)) edges between (A) and (B). On the other hand each (b\in B) is connected to (\ell) nodes in (A). Therefore, (|B|=k(k-1)/\ell). Thus (|G(k,\ell)|=|\{v\}\cup A\cup B|=1+k+k(k-1)/\ell).

The real question is whether (G(22,6)) exists?

Some necessary conditions are (\ell) divides (k(k-1)) from our formula for the size of the graph, and (k) is even since there are (\frac k2) edges in the graph. But these are not sufficient: It looks like (G(4,4)) exists but (G(4,3)) does not.

haha, my algebra skills were way off here, you are right. i've fixed it.

 

[lordvid]

Can people post solutions for questions without using LaTeX? Those of us with phones cannot see anything, and it's frustrating...

Anyways, a non-algebraic counting method is as follows:

This method shows the existence of a solution and (with no re-labelling) the construction shows the uniqueness of the solution.

First, fix a Santa. Call this GROUP 1
This Santa has 22 friends. Call this group of people GROUP 2. None of the 22 people in GROUP 2 are friends.
Now, each of the 22 Santas in GROUP 2 has 21 additional friends, in addition to the Santa in GROUP 1. Call this group of additional friends GROUP 3. How many individuals are in GROUP 3?
Well, imagine the friendships as "edges" connecting a Santa in GROUP 2 to the friend in GROUP 3, that is an edge connecting the Santas ("nodes") in GROUP 2 and a Santa ("node") in GROUP 3. There are 22*21 such edges. But because each of the Santas in GROUP 2 do not know each other, they must also have 6 mutual friends. That is, each Santa in GROUP 2 has an edge that leads to the same node in GROUP 3 as 5 other Santas in GROUP 2. Imagine picking up these nodes in GROUP 3 and putting them on top of one another. This is the same as dividing 22*21 by 6. So we still have 22*21 edges, but we have 22*21/6 nodes ( that is, 22*21/6 Santas) in GROUP 3.

Now, we need to stop and think. Consider a Santa in GROUP 3. What about the friends of this Santa who are not in GROUP 2 or GROUP 3? Call this GROUP 4.
How many people are in GROUP 4?

Consider a Santa in GROUP 4. This Santa is not friends with the Santa in GROUP 1 (our original Santa). So this GROUP 4 Santa has 6 mutuals friends with the GROUP 1 Santa. But all of GROUP 1 Santa's friends are in GROUP 2. And all of GROUP 2 Santas' friends are in GROUP 3! So our GROUP 4 Santa can have no mutual friends with our GROUP 1 Santa! If a Santa exists in GROUP 4, he must have exactly 6 mutual friends with our GROUP 1 Santa! This means there is no one in GROUP 4! This means that all the Santas are accounted for in GROUPS 1, 2, and 3.

Total in GROUPS 1, 2 and 3 = 1 + 22 + 21*22/6 = 100.

Since the construction leads to a unique group of individuals in GROUP 1, 2 and 3 (except re-labelling)....our group is finite and unique!

 

[Andy Nguyen]

Can people post solutions for questions without using LaTeX? Those of us with phones cannot see anything, and it's frustrating...

Vid
Do you use your phone browser or Tapatalk? Can you send me a screenshot of what latex looks like to me? Everything looks fine to me on my Android phone.

 

[Brad Warren]

The real question is whether \(G(22,6)\) exists?

Some necessary conditions are \(\ell\) divides \(k(k-1)\) from our formula for the size of the graph, and \(k\) is even since there are \(\frac k2\) edges in the graph. But these are not sufficient: It looks like \(G(4,4)\) exists but \(G(4,3)\) does not.

There are \(\frac{nk}{2}=\frac{k}{2}(1+k+\frac{k(k-1)}{l})\) edges. Either k or \(\frac{k(k-1)}{l}\) has to be even. I think those conditions are sufficient.

Never mind, that doesn't explain why G(4, 3) doesn't exist. But k does not have to be even.

 

[lordvid]

Some necessary conditions are \(\ell\) divides \(k(k-1)\) from our formula for the size of the graph, and \(k\) is even since there are \(\frac k2\) edges in the graph. But these are not sufficient: It looks like \(G(4,4)\) exists but \(G(4,3)\) does not.

Can you show how to show G(4,4) exists, but G(4,3) does not?

G(4,3) does exist, I think....1 + 4 + 4*3/3 or GROUP 1 is 1 person, GROUP 2 is 4 people, GROUP 3 is additional 4 people...

If I'm doing something wrong, please correct...

 

[Brad Warren]

Can you show how to show G(4,4) exists, but G(4,3) does not?

G(4,3) does exist, I think....1 + 4 + 4*3/3 or GROUP 1 is 1 person, GROUP 2 is 4 people, GROUP 3 is additional 4 people...

If I'm doing something wrong, please correct...

For G(4,4), there are 2 groups of 4 such that all santas are friends with everyone in the other group.

For G(4,3), there are 4 santas in GROUP 2 that each need to have 3 friends in GROUP 3, but they must also have only 2 mutual friends in GROUP 3 (the third mutual friend is the first santa). Therefore, each santa in GROUP 3 has 3 friends in GROUP 2. But they need a 4th friend, and it can't be in GROUP 3 because they share mutual friends with eachother, so it is impossible.

 

[MiloRambaldi]

There are \(\frac{nk}{2}=\frac{k}{2}(1+k+\frac{k(k-1)}{l})\) edges. Either k or \(\frac{k(k-1)}{l}\) has to be even. I think those conditions are sufficient.

Never mind, that doesn't explain why G(4, 3) doesn't exist. But k does not have to be even.

You're right about \(k\) (I incorrectly said \(\frac k2\) edges).

 

[MiloRambaldi]

For G(4,4), there are 2 groups of 4 such that all santas are friends with everyone in the other group.

Nice observation: For all \(k\), \(G(k,k)\) is the complete bipartite graph \(\mathbf{K}_{k,k}\).