- Joined
- 5/25/10
- Messages
- 417
- Points
- 53
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.