At a meeting of $ 12k$ people, each person exchanges greetings with exactly $ 3k+6$ others. For any two people, the number who exchange greetings with both is the same. How many people are at the meeting?
Problem
Source: IMO Shortlist 1995, N5
Tags: combinatorics, graph theory, Extremal combinatorics, IMO Shortlist
12.08.2008 23:12
Once again, it looks like it's time to count the same thing twice. This time we will count ordered triples of distinct people $ (A,B,C)$ such that $ B$ greeted both $ A$ and $ C$. Let $ m$ be the number of people who exchanged greetings with any two given people. Method 1: There are $ 12k$ choices for $ A$. Once $ A$ is chosen there are $ 3k+6$ choices for $ B$, and once $ B$ is chosen there are $ 3k+5$ choices for $ C$. This gives $ 12k(3k+5)(3k+6)$. Method 2: There are $ 12k$ choices for $ A$. There are then $ 12k-1$ choices for $ C$. Once $ A$ and $ C$ are chosen, there are $ m$ choices for $ B$, for a total of $ 12k(12k-1)m$. Solving, $ m=\frac{(3k+5)(3k+6)}{12k-1}=\frac{1}{4}(35+11+\frac{3k+131}{12k-1})=\frac{1}{4}(3k+11+\frac{1}{4}(1+\frac{525}{12k-1}))$. Now $ 525=3*5^2*7$, and it can easily be checked that $ 35$ is the only factor of $ 525$ that is one less than a multiple of $ 12$. Therefore $ k=3$, and $ 36$ people are at the meeting. To show that this is actually possible, consider each person as being labeled by an ordered pair $ (x,y)$, where $ 1 \leq x,y \leq 6$. Person $ (x,y)$ shakes hands with person $ (w,z)$ if either $ x=w$, $ y=z$, or $ x+y$ is congruent to $ w+z$ modulo $ 6$.
29.09.2009 18:40
I will repeat my post on a topic with same statement http://www.mathlinks.ro/viewtopic.php?t=301854 The problem describes a graph $ G = (V,E)$ with $ |V| = n = 12k$ vertices and $ d = 3k + 6$, the degree of each vertex (i.e. the number of edges incident in that vertex). Such a graph is called $ d$-regular. Moreover, it is given that for any two vertices, the number of other vertices joined to both those two is the same, be that constant $ \lambda$. Usually we denote the degree of a vertex $ x$ by $ \deg x$, and the set of its neighbors (joined to him by edges) by $ N(x)$, so we are given that $ \deg x = d$ for all $ x \in V$ (i.e. $ d(G) = d$), and $ | N(x) \cap N(y) | = \lambda$ for all distinct $ x,y \in V$. In fact what it is described here is a symmetric balanced incomplete blocks design (BIBD), with parameters $ (n, d, \lambda)$. But it is immediate, by a little double-counting, that the relation $ \lambda(n - 1) = d(d - 1)$ is necessary; in our case $ \lambda(12k - 1) = (3k + 6)(3k + 5)$. It is relatively easy to prove that this may happen only for $ k = 3$ (therefore $ \lambda = 6$). The question now is if a $ (36, 15,6)$ symmetric BIB actually exists (the fact that the numbers check the relation above is not always sufficient). The good news is that these numbers verify the condition of the Bruck-Ryser-Chowla theorem ($ 36$ is even, and $ 15 - 6 = 9$ is a perfect square), but that is also just necessary, not sufficient. I cite from the link is http://crosbi.znanstvenici.hr/prikazi-rad?chset=ASCII&lang=EN&rad=56134 Up to isomorphism there are $ 4$ symmetric $ (36, 15, 6)$ designs with automorphisms of order $ 7$, and $ 38$ symmetric $ (36, 15, 6)$ designs with automorphisms of order $ 5$. For those designs full automorphism groups are determined. Also, all symmetric $ (36, 15, 6)$ designs having automorphisms of order $ 3$ acting with $ 9$ and $ 6$ fixed points, or cyclic automorphism groups of order $ 4$ acting standardly are constructed and orders of their full automorphism groups are determined. See also, best, http://www.uow.edu.au/~jennie/WEB/WEB69-93/max/005_1969.pdf
29.09.2009 19:10
I cite from IMO-Compendium (SL-95-19, p. 596): For each two people let $ n$ be the number of people exchanging greetings with both of them. To determine $ n$ in terms of $ k$, we shall count in two ways the number of triples $ (A,B,C)$ of people such that $ A$ exchanged greetings with both $ B$ and $ C$, but $ B$ and $ C$ mutually did not. There are $ 12k$ possibilities for $ A$, and for each $ A$ there are $ (3k + 6)$ possibilities for $ B$. Since there are $ n$ people who exchanged greetings with both $ A$ and $ B$, there are $ 3k + 5 - n$ who did so with $ A$ but not with $ B$. Thus the number of triples $ (A,B,C)$ is $ 12k(3k + 6)(3k + 5 - n)$. On the other hand, there are $ 12k$ possible choices of $ B$, and $ 12k-1-(3k+6) = 9k-7$ possible choices of $ C$; for every $ B$, $ C$, $ A$ can be chosen in $ n$ ways, so the number of considered triples equals $ 12kn(9k - 7)$. Hence $ (3k + 6)(3k +5 - n) = n(9k - 7)$, i.e., $ n =\frac{3(k+2)(3k+5)} {12k-1}$. This gives us that $ \frac{4n} {3} = \frac{12k^2+44k+40} {12k-1} = k + 4 - \frac{3k-44} {12k-1}$ is an integer too. It is directly verified that only $ k = 3$ gives an integer value for $ n$, namely $ n = 6$.
22.08.2019 15:40
Man, I really liked this problem... such a simple idea, but still took me quite a while to find it- anyways here's a sketch of my proof. First let's construct a graph with vertices $a_1,a_2,a_3,...,a_{12k}$ such that there exists an edge between $2$ vertices iff they greet each other- hence there are $3k+6$ edges emanating from each vertex.
). But, we already know the graph is $(3k+6)$-regular, and as there are $12k$ vertices, there must be $(12k) \cdot \binom{3k+6}{2} =\frac{12k(3k+6)(3k-5)}2$ points in total! This almost solves the problem for us, all we have left is figuring out how to exploit this information about the point tally and perhaps a little bashing at the end... To overcome the first dilemna, first let's define the magnitude of the intersection of a two-element set $=t$ (using the fact that the intersection of a $2$ element of a set always has the same magnitude). Thus, the total number of points must just simply be $t \cdot (\text{number of 2-element subsets}) =t \cdot \binom{12k}{2}$ (looking back, this was the motivation for defining our point tally the way we did) $=> \frac{12k(12k-1)}{2} \cdot t = \frac{12k(3k+6)(3k-5)}2 => t \cdot (12k-1) = 3(k+2)(3k+5)$. Time to gcd bash a little, perhaps? As $12k-1 \mid (3k+6)(3k+5) => 12k-1 \mid (k+2)(3k+5) =>12k-1 \mid 4(k+2)(3k+5) =>12k-1 \mid 12k^2+44k+40 => 12k-1 \mid 45k+40$. Thus $45k+40 =m(12k-1) => k(12m-45)=m+40$- obviously, for $m \geq 9$, $k$ can't be an integer, thus we only need to check for $m$ taking values from $1$ to $8$, and we get our integral solution when $m=5$ $=>k=3$. Hence there are $12 \cdot 3 = \fbox{36}$ people at the meeting.
31.12.2019 19:09
09.08.2021 19:12
Such a good exercise for double counting Solution: We will count the quantity $S=$number of triplets $(A,B,C)$ of peoples in the meeting. such that $C$ exchanges greetings with both $A$ and $B$ Let: For each pair $A,B$ in the meeting, There are $m$ peoples greeting with both of them. First, Select pairs $A,B$ first then, choose $C$. There are$S=\binom{12k}{2}m$ ways Second, Select $C$ first, Then Choose pairs $A,B$ with both of them greeting with $C$. There are $S=12k\binom{3k+6}{2}$ ways Therefore, $$\binom{12k}{2}m=12k\binom{3k+6}{2}$$After some calculation and divisible theory, We get $12k-1|175$ Therefore, $k=3$. The Construction for $k=3$(to see that this actually work) Consider the following $6\times 6$ matrix: $$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 4 & 5 & 6 & 1 \\ 3 & 4 & 5 & 6 & 1 & 2 \\ 4 & 5 & 6 & 1 & 2 & 3 \\ 5 & 6 & 1 & 2 & 3 & 4 \\ 6 & 1 & 2 & 3 & 4 & 5 \end{pmatrix} $$Each indice represents peoples, For the people labeled $i$ greeting with the peoples in the same row/column and the peoples with the same labeled So, there are $12\times3=36$ peoples in this meeting.
18.09.2021 16:08
Quite simple and cute. Let the set $F=(1,2,... 12k)$,which denotes the people in the meeting. Let set $A_{i}$ denote the people with whom person $i$ shared greetings with. It is known $|A_{i}|=3k+6$ and $|A_{i} \cap A_{j}|=s$,for every $(i,j)$ Now counting the number of triples $(A_{i},A_{j},l)$ where the first two sets share an element $l$. We get that $ s \binom{12k}{2} = 12k \binom{3k+6}{2}$,which ultimately results in finding $k$ such that $12k-1|3k^2+11k+10$ which after some division algorithm,results in finding $k$ such that $12k-1|9k+43$ which can be computed manually to give $k=3$ and hence the answer is $36$.