You are at a strange party where everybody knows exactly 22 people. Of the 22 people that each person knows, none of them know each other. But all the people in the room who dont know each other have exactly 6 mutual friends present. How many people are at the paarty?

anybody?

12population = Range[12]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}friends = Join[{Range[2, 7]}, ConstantArray[Prepend[Range[8, 12], 1], 6], ConstantArray[Range[2, 7], 5]]{{2, 3, 4, 5, 6, 7}, {1, 8, 9, 10, 11, 12}, {1, 8, 9, 10, 11, 12}, {1, 8, 9, 10, 11, 12}, {1, 8, 9, 10, 11, 12}, {1, 8, 9, 10, 11, 12}, {1, 8, 9, 10, 11, 12}, {2, 3, 4, 5, 6, 7}, {2, 3, 4, 5, 6, 7}, {2, 3, 4, 5, 6, 7}, {2, 3, 4, 5, 6, 7}, {2, 3, 4, 5, 6, 7}}friendships = Union[Map[Sort, Flatten[Table[Table[{j, friends[[j, k]]}, {k, 1, Length[friends[[j]]]}], {j, 1, Length[friends]}], 1]]]{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {2, 8}, {2, 9}, {2, 10}, {2, 11}, {2, 12}, {3, 8}, {3, 9}, {3, 10}, {3, 11}, {3,12}, {4, 8}, {4, 9}, {4, 10}, {4, 11}, {4, 12}, {5, 8}, {5, 9}, {5, 10}, {5, 11}, {5, 12}, {6, 8}, {6, 9}, {6, 10}, {6, 11}, {6, 12}, {7, 8}, {7, 9}, {7, 10}, {7, 11}, {7, 12}}Map[Count[friendships, #, {2}] &, population]{6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6}forbiddenfriendships = Union[Join[Union[Map[Sort, Permutations[Range[2, 7], {2}]]], Union[Map[Sort, Permutations[Prepend[Range[8, 12], 1], {2}]]]]]{{1, 8}, {1, 9}, {1, 10}, {1, 11}, {1, 12}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {8, 9}, {8, 10}, {8, 11}, {8, 12}, {9, 10}, {9, 11}, {9, 12}, {10, 11}, {10, 12}, {11, 12}}Intersection[friendships, forbiddenfriendships]{}

Tricksy, brainteaser! Without the "mutual friends" constraint, the answer is infinite. Consider a simpler version in which everyone knows 2 people and none of them know each other.Thus, you would know persons p1, p2Person p1 would know persons p11 and p12Person p2 would know persons p21 and p22Person p11 would know persons p111 and p112.... and so on , doubling to infinite with each tier.In the case in which "everybody knows exactly 22 people", the fan-out is 22 so the progression would be 1 (you), 22, 284, 10648, ....I'll post more on the effects of the mutual friends later.....

It cant be 12 because everybody in the room knows 22 other people in the room

Yes, its a tricky one alright, I think I must have spent two days thinking about it on and off before solving it. THe mutual constraint stops it being infinite like you said.

I suspect that 1+22+484 is the upperbounds because the 484 provide a nice population for mutual friends of unknown people. But whether this pulls the total down from 1+22+22^2 to something like 1+22+22*16 will require a little more thought....

QuoteOriginally posted by: outrunless than 22*21 maybe 22*16?Actually I was going to say that the solution is bounded below by 23 and above by the Graham's number

Im interested to see where this is going. So is the number of nodes on the circle the answer?

ruairih, if friend/knowing is mutual, i.e., if A is a friend of/knows B, then B is a friend of/knows A, then the answer seems to be 100 people. my approach / hint is to count the groups of 3 people with only one pair not knowing each other (A knows B and C, but B and C do not know each other)of course one then needs to construct an explicit example, which should be straightforward.

Yes, Wileysw has the correct answer, I did it the same way after drawing a sort of schematic diagram. Im interest to see how this is done by a more brute force method too.