• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

Santas at Christmas party

radosr

Baruch MFE Faculty
Joined
7/18/07
Messages
640
Points
73
You and other Santas are at a Santas-only party where every Santa knows exactly 22 other Santas. Among the 22 Santas each Santa knows none know each other. But, any two Santas who do not know each other have exactly 6 mutual friends present. How many Santas are at the party?
 
It is not a trick question. There is a solution!
 
You and other Santas are at a Santas-only party where every Santa knows exactly 22 other Santas. Among the 22 Santas each Santa knows none know each other. But, any two Santas who do not know each other have exactly 6 mutual friends present. How many Santas are at the party?

One.

edit: at most.
 
It is not a trick question. There is a solution!
IF such a graph exists, I can prove that there must be 100 Santas.

But it seems more difficult to prove that there is such a graph with 100 nodes (I'm still thinking about it). It is a trick question if there is no such graph.
 
o_O It seems to me this question is not being considered seriously :).
The correct answer is definitely more than one.
Sorry. My answer was based on the assumption that there is only one Santa and he lives in Rovaniemi.
Happy Christmas.
 
I think it is 100 also. I didn't use a graph/node method, I just counted, setting people up in groups and then reasoning for the need for new people, etc. but there is no way I am typing all of that up. suffice to say that
Total = 1 + 22+ 21*22/6 = 100.
I'm not sure though, and there must be a better way to doing this than sitting here talking to yourself. If there is an elegant solution using graphs...somebody please post.
 
I think it is 100 also. I didn't use a graph/node method, I just counted, setting people up in groups and then reasoning for the need for new people, etc. but there is no way I am typing all of that up. suffice to say that
Total = 1 + 22+ 21*22/6 = 100.
I'm not sure though, and there must be a better way to doing this than sitting here talking to yourself. If there is an elegant solution using graphs...somebody please post.

It looks exactly like what I did: Fix one Santa. Each of the 22 Santas connected to the first Santa is connected to 21 other Santas (other than the first and the 22 connected to the first). Then observe that each of these 22 * 21 Santas is being counted exactly 6 times.
 
I get 100 too.

Assume there are (n) santas at the party. There are (\frac{n(n-1)}{2}) potential relationships between them. Of these, (\frac{22n}{2} = 11n) are friendships. Therefore, (\frac{n(n-1)}{2}-11n) are non-friendships.

For each non-friendship there are (6\cdot 2=12) friendships that arise from it. And conversely, each friendship arises from a non-friendship in this way: if A and B are friends, then one of A's other friends, C, is not friends with B, but A is a mutual friend. This gives a total of (12\cdot \left[\frac{n(n-1)}{2} - 11n\right]=6n(n-1)-132n) friendships. But each friendship is counted (2\cdot 21 = 42) times in this total: once for each of the 21 non-friendships that A has with B's circle of friends, and once for the 21 non-friendships that B has with A's circle of friends. So the actual number of friendships is (\frac{6n(n-1) - 132n}{42}).

Setting this equal to (11n) and solving gives n=100.
 
I get 56.
...
So the actual number of friendships is (\frac{6n(n-1) - 132n}{42}).
Setting this equal to (11n) and solving gives n=56.

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.
 
Back
Top