6
$\begingroup$

At a party, everybody is friend with exactly $22$ of the other persons present. Whenever two persons are friends, they do not have any friends in common. Whenever two persons are not friends, they have exactly six friends (present at the party) in common.

Question: How many persons are at the party?

(Note: Friendships are always mutual. Nobody is friend with himself.)

$\endgroup$
  • 5
    $\begingroup$ You should specify that the party is not empty, which would make all of the conditions vacuously true :) $\endgroup$ – Lynn Nov 25 '15 at 13:34
  • 2
    $\begingroup$ @Mauris The question could have been a trick question where the answer was "There is no one at the party" :) $\endgroup$ – Ivo Beckers Nov 25 '15 at 14:12
  • 1
    $\begingroup$ @Mauris If no one is at the party, a person could not be friends with "exactly 22 of the other persons present." $\endgroup$ – GentlePurpleRain Nov 25 '15 at 17:27
  • 4
    $\begingroup$ @GentlePurpleRain If there is nobody at the party, any statement about everybody is vacuously true. $\endgroup$ – Petr Pudlák Nov 25 '15 at 17:32
  • 4
    $\begingroup$ If there's nobody there, can it even still be considered a party? I don't think you can treat the word "party" the same as "set" - e.g. there cannot be an "empty party". $\endgroup$ – Darrel Hoffman Nov 25 '15 at 17:40
10
$\begingroup$

Update: I read up a bit more and I am pretty sure of my answer now.


Is the answer

$100$?

I searched for "22 graph" on Google and a link came up called the Higman-Sims graph.

I do not know anything about , but the first line on the page looked very similar to your question.

In mathematical graph theory, the Higman–Sims graph is a 22-regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph with 100 vertices and valency 22, where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors.

$\endgroup$
9
$\begingroup$

As pointed out by ghost_in_the_code

100

is a solution, however he doesn't state why it's the only solution.

To show it is the only solution we have to realize that what is asked is how many vertices are there in $srg(v,22,0,6)$ where $srg(v, k, λ, μ)$ is defined as the strongly regular graph with:

  • $v$ vertices
  • degree $k$
  • Every two adjacent vertices have λ common neighbours.
  • Every two non-adjacent vertices have μ common neighbours.

As explained on this wiki-page the following relation is always true:

$(v-k-1)\mu = k(k-\lambda-1)$

Filling in our numbers we get
$(v-23)6 = 22(21)$

This gives the unique solution

$v=100$

$\endgroup$
1
$\begingroup$

I did this in my head and multiplied two numbers with a calculator to get 184 = 8 x 23.

At a party, everybody is friend with exactly 22 of the other persons present.

1) The way I thought it out was if there were 23 people at the party then each person would be friends with the other 22.

Whenever two persons are friends, they do not have any friends in common.

2) There could be n groupings of 23

Whenever two persons are not friends, they have exactly six friends (present at the party) in common.

3) Which tells me there can be a minimum of 8 groupings. (2 groupings contain the two non-friends, the other 6 groupings contain the 6 common friends from Person from Group1 and Person from Group2.

Here's a picture, imagine each black circle contains 23 dots.

enter image description here

Red dots signify the two non-friends.

Green dots signify the common friends of each of the red dots.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.