Easy: Suppose $A$ belongs to clubs $C_1,C_2...C_a$, then in these clubs A apears in $\sum|C_i|-1$ pairs, so we get this sum is equal to $10000$. and since every of these clubs is in $\frac{|C_i|-1}{2}$ societies, $A$ appears in $5000$ societies. Now every Society contains $10001$ students, so we easily get, counting edges in the bypartite graph formed by students and societies, and an edge if a student goes in that society that $k=5000$

I think that you could probably eliminate one of conditions (1) and (2) and it would probably still be sufficient to solve the problem (Pascual's solution doesn't look like it really uses condition (2), for example).

Is there a proof that those conditions are met :

Pretty straightforward problem. Label the students $s_1, s_2, \cdots , s_{10001},$ the clubs $C_1, C_2, \cdots , C_n$ and the societies $S_1, S_2, \cdots , S_k.$ Let the number of students in club $C_i$ be $2f(C_i)+1,$ and let $g(S_i)$ denote the number of clubs in society $S_i.$ The last condition implies that club $C_i$ is in exactly $f(C_i)$ societies. Now, for any club $C_i,$ there are $\dbinom{2f(C_i)+1}{2} = f(C_i) (2f(C_i)+1)$ pairs of students. Since each pair of students is in a unique club, $\displaystyle \sum_{i=1}^{n} f(C_i) (2f(C_i)+1)$ must denote the total number of student pairs, so $\displaystyle \sum_{i=1}^{n} f(C_i) (2f(C_i)+1) = \dbinom{10001}{2}.$ Now, each student is contained in exactly one club of a society, so a society contains exactly 10001 students. The total number of students (counted with multiplicity) in all societies is hence $10001 \times k.$ However, the sum of number of students of all societies is also equal to the sum of the number of students in each club times the number of times that club appears in all the societies, so $10001 \times k = \displaystyle \sum_{i=1}^{n} f(C_i) (2f(C_i)+1).$ Combining them, we easily get that $k=5000.$ For equality, set $f(C_1)=10001, f(C_2) = f(C_3) = \cdots = 0$ and $g(S_1) = g(S_2) = \cdots = g(S_{5000}) = 1$ where $C_1 \in S_i \quad \forall \ i.$

Standard problem. Simply double count the number of ordered triples (P,C,S) where student P is in a club C of society S. The second condition gives $T=10001k$ triples. The third condition gives $T$ is the sum over all clubs of $m(2m+1)$. To make use of the first condition, simply double count the number of triples (P1,P2,C) where students P1, P2 are in the same club C. You get: the sum over all clubs of (2m+1) choose 2 is equal to 10001 choose 2. Multiply both sides by 2 and equate with T to solve for

Easy:Count (student,club,society) such that student is in club and club is in society.

Nothing different, but I was solving this recently, so here goes Let there be $t$ clubs $C_1 , C_2, \cdots C_t$. Consider the set $$X = \{ (s , C , S) | s \in C , C \in S, s \text{ is a student } , C \text{ is a club, and } S \text{ is a society.} \} $$ We calculate $|X|$ in two ways. First fix $s$ and $S$. From (ii), there is exactly one club $C_i$ for which $(s,C_i,S) \in X$. Thus $$|X| = 10001k.$$ Now fix the club, say $C_i$. It has $|C_i|$ students, and it belongs to $\frac{|C_i| - 1}{2} $ societies from (iii). Thus $$|X| = \sum_{i=1}^t \frac{|C_i|(|C_i|-1)}{2}.$$ Now consider the set $$Y = \{( \{s_1 , s_2\} , C) | s_1 , s_2 \text{ are different students belonging to the club } C.\}$$ Again, we calculate $|Y|$ in two ways. First fix $C = C_i$. There are ${|C_i| \choose 2}$ such pairs of students in the club. Thus $$|Y| = \sum_{i=1}^t {|C_i| \choose 2} $$ Now fix the pair $\{s_1 , s_2\}$. From (i), there is exactly one club $C$ for which $(\{s_1,s_2\} , C) \in Y$. Therefore $$|Y| = {10001 \choose 2}$$ From all these relations, we have $$10001k = |X| = \sum_{i=1}^t \frac{|C_i|(|C_i|-1)}{2} = \sum_{i=1}^t {|C_i| \choose 2} = |Y| = {10001 \choose 2}$$so that $$k = 5000.$$ To show that $k=5000$ indeed works, consider just $1$ club $C$ (that is, $t=1$) which belongs to $5000$ societies and such that all students are a member of this club. Clearly (i),(ii) and (iii) are satisfied.

Fix a student $T$ and let $C_1, C_2, \dots, C_r$ be all the clubs he is in. By the first condition, $$\sum _{i=1}^r |C_i| = 10000+r$$From the second condition, each society has exactly all the students in the university. So $T$ appears $k$ times in all $k$ societies exactly once. Moreover, the clubs within each society is disjoint. So $C_1, C_2, \dots , C_r$ are in different societies. From the third condition, observe that each $C_i$ appears in $\frac{|C_i|-1}{2}$ societies. So combining this with the previous equation,$$k = \sum _{i=1} ^r \frac{|C_i|-1}{2} = \frac{10000+r-r}{2} =5000$$ Now a construction for $k=5000$. Put all students into just one club and put this club in each of $5000$ societies. We are done.

Let us write n= 10001.Denote by T the set of ordered triples (a,C,S ), where a is a student, C a club, and S a society such that a∈C and C∈S . We shall count|T |in two different ways. Fix a student a and a society S. By (ii), there is a unique club C such that (a,C,S )∈T .Since the ordered pair(a,S ) can be chosen in nk ways,we have that|T |= nk. Now fix a club C. By (iii), C is in exactly (|C|−1)/2 societies, so there are |C|(|C|−1)/2 triples from T with second coordinate C. If C is the set of all clubs, we obtain|T |= ∑C∈C |C|(|C|−1) 2 . But we also conclude from (i) that ∑ C∈C |C|(|C|−1) 2 = n(n−1) 2 . Therefore n(n−1)/2= nk, i.e., k = (n−1)/2= 5000. On the other hand, for k = (n−1)/2 there is a desired configuration with only one club C that contains all students and k identical societies with only one element (the club C). It is easy to verify that (i)–(iii) hold.

The value $k=5000$ is achieved if there is exactly one club, and $5000$ societies consisting of only that club. We show it's the only value. Condition (i) implies \[ \binom{10001}{2} = \sum_{C \text{ club}} \binom{|C|}{2} \]On the other hand, condition (ii) means that each individual society is a set of clubs whose disjoint union is all $10001$ students, so we have \[ k \cdot 10001 = \sum_{C \text{ club}} |C| \cdot \frac{|C|-1}{2} \]where $\frac{|C|-1}{2}$ comes from (iii). From these two equations we see $k = 5000$ is the only possible value.

Let $C$ be the number of clubs and let $k_1 , k_2 , \dots , k_{C}$ be the number of students that each club has. First, we count the number of triplets $(s_1 , s_2 , c)$ where $s_1 , s_2$ are students whose common club is $c$. If we fix the students, there is only one way to choose $c$ so there are $\binom{10001}{2}$ triplets. If we fix the $c$ first, then there are exactly $\binom{k_1}{2} + \binom{k_2}{2} + \dots + \binom{k_C}{2}$ triplets. Thus, we have that $\sum_{i=1}^{C} \binom{k_i}{2} = 10001\cdot 5000$. Now, we count the triplets $(s,c,t)$ where $s$ is a student, $c$ is student's one of the clubs, $t$ is this club's one of the societies. If we fix the student and society, there is only one way to choose $c$ so there are $10001k$ such triplets. If we fix the club, then there are exactly $\frac{k_1(k_1 - 1)}{2} + \dots + \frac{k_C(k_C - 1)}{2} = \sum_{i=1}^{C} \binom{k_i}{2} = 10001\cdot 5000$ such triplets. Thus, we have $10001k = 10001\cdot 5000 \implies k=5000$. It is easy to construct an example for $k=5000$. Let there be only one club and all the students are joined to this club, and this club is in every society. It is clear that this works and we are done. $\square$

We claim that the only possible value of $k$ is $\boxed{5000}$. This can be achieved if there is one club consisting of everybody, and that club is in $5000$ societies. Consider a person $A$. Condition (i) implies that the set of clubs containing $A$ contain every other person exactly once. Since every club has an odd number of people, for every club containing $A$ the other students must come in pairs. However, notice that if a club containing $A$ contains $k$ other pairs of students, it will have $2k+1$ people overall and thus must be in $k$ societies. There are $10000$ other people, and therefore $5000$ pairs of other people. Thus there are a total of $5000$ societies that the clubs containing $A$ are in. Since no society can contain two clubs with $A$ in them, all $5000$ of these societies are distinct. Furthermore, the presence of another society would imply that there is a society with no club containing $A$, a clear contradiction. The proof is complete.

ISL marabot solve Consider a random student $P$ and let $S$ be the set of clubs $P$ is in. By the first condition, every other student is in exactly one of the clubs in $S$. Now consider some club in $S$. Suppose it has $p$ disjoint pairs of students excluding $P$. Then it must be in $p$ societies. Since there are totally $5000$ pairs, $P$ must be in $5000$ societies. The existence of another society implies that $P$ is not in it, a contradiction. So the only possible value of $k$ is $\boxed{5000}$. This is achievable if there is exactly one club that consists of everyone and it is in $5000$ societies.

success is 99% understanding the problem, 0.99% perspiration and 0.01% inspiration. Let $S$ be the number of ways to pick a society, a club in that society, and a student in that club. Picking the society and the student, we know that there exists exactly one club that satisfies the conditions. Thus, $S=10001k.$ Now let the clubs have $c_1,c_2,\dots,c_n$ people, respectively. These clubs belong to $\frac{c_1-1}{2},\frac{c_2-1}{2},\dots,\frac{c_n-1}{2}$ societies, respectively. Thus, $S=\sum_{n}^{i=1}{\binom{c_i}{2}}.$ This is summing the number of pairs of people in any given club over all clubs. However, each pair of people is in exactly one club so this is just $\binom{10001}{2}.$ Thus, $k=5000.$ This is reachable with just one club with all the people, and this club is in all the societies.

The answer is $k=5000$. This is achievable with one club of all $10001$ people in $5000$ societies. This can easily be seen to work. Let the clubs be $C_1,C_2, \cdots, C_k$ and the people be $P_1,P_2, \cdots , P_{10001}$. We count the number of triples $(P,C,S)$ where $S$ is a society, $C$ is a club in $S$, and $P$ is a person in $C$. Note that if we pick the club first we have that this sum is $$\sum_{C \text{ club}} |C_i| \cdot \frac{|C_i|-1}{2} = \sum_{C \text{ club}} \binom{|C_i|}{2}$$using condition (iii). Next note that $$\sum_{C \text{ club}} \binom{|C_i|}{2} = \sum_{\text{unordered pair } (P_i, P_j) \text{ in club } C} 1 = \binom{10001}{2},$$where the last equality follows from condition (ii). Next, if we pick the person and society first, the club is automatically chosen so the sum is $10001k$. This means $10001k=\binom{10001}{2}$, so $k=5000$.

Nice problem

Let $C_i,$ where $1\le i\le \ell,$ be the size of the clubs. By (i), we see $$\binom{10001}{2}=\sum_{i=1}^{\ell}\binom{C_i}{2}.$$Notice by (ii), all students must be part of any society. Hence, if we want to choose a student, a club, and a society (such that the student is in the club is in the society), we can just choose the society and then choose any student, which we can do in $10001k$ ways (this would also determine the club by (ii)). Alternatively, we can proceed by casework on which club the student is in. For each club $C_i,$ we can choose $C_i$ students and $\frac{C_i-1}{2}$ societies by (iii). Thus, we see $$10001k=\sum_{i=1}^{\ell}C_i\cdot\frac{C_i-1}{2}.$$This implies $k=5000.$ This works by letting all the students be in one club which is part of $5000$ societies. $\square$

Let there be $c$ clubs. For each club, let the number of members in it be $a_1,a_2,\dots,a_c$. From the first condition, clubs contribute distinct pairs to all student pairs: $$\binom{10001}{2}=\binom{a_1}{2}+\binom{a_2}{2}+\dots+\binom{a_c}{2}.$$From the second and third conditions, each club contributes $(2m+1)m$ student-society pairs: $$10001k=\binom{a_1}{2}+\binom{a_2}{2}+\dots+\binom{a_c}{2}.$$We see that the two equations have equivalent right hand sides, so $k=\boxed{5000}$. This can be achieved by just having every student in $1$ club, which is in all $5000$ societies. QED.

We claim that the answer is $k=5000$. This can be achieved by having 1 club that contains all of the students and is in all 5000 societies. Suppose that there are $n$ clubs, and let club $i$ have $2m_i+1$ students. From condition (i), we have $${2m_1+1 \choose 2}+{2m_2+1 \choose 2}+\cdots +{2m_n+1 \choose 2}={10001 \choose 2},$$since both sides are equal to the number of pairs of students. Consider the number of triples $(a,b,c)$ such that club $b$ contains student $a$ and is in society $c$. By summing over all clubs, this is equal to $$m_1(2m_1+1)+m_2(2m_2+1)\cdots +m_n(2m_n+1).$$However, condition (iii) tells us that this is also equal to $10001k.$ Therefore, we have $$m_1(2m_1+1)+m_2(2m_2+1)\cdots +m_n(2m_n+1)=10001k.$$However, note that $m_i(2m_i+1)={2m_i+1\choose 2},$ so combined with our equation from condition (i), we have $${10001\choose 2}=10001k\rightarrow k=5000,$$so we are done.

Double count pairs $(s, C, S)$ where student $s$ belongs in club $C$, which belongs in society $S$. For every pair $(s, S)$, there exists a unique $C$, so there are $10001k$ such tripltets. On the other hand, for every $C$, there exsit $m(2m+1)$ pairs for $2m+1$ students in club $C$. But then $$\sum_C {2m+1 \choose 2} = \sum_C m(2m+1) = 5000 \cdot 10001,$$so thus we must have $k=5000$. For a construction, put all students in one club, which is part of all $5000$ societies.

This solution uses the deep fact that $\binom{2m+1}{2}=m(2m+1)$. For a club $c$ let $s(c)$ denote the number of societies it belongs to. Then $\sum s(c)(2s(c)+1)=\sum \binom{2s(c)+1}{2}$ over all clubs $c$ will count both the number of pairs of students and the number of student-society pairs. There are $10001\cdot 5000$ of the former so we obtain $k=5000$ only. A construction is to create a single club which belongs for some reason to $5000$ societies and put every student into it.

combo is hard The answer is $k = 5000$. Let the clubs be $C_1, C_2, C_3 ... C_i$. Then condition i) tells us that \[ \dbinom{10001}2 = \sum \dbinom{|C_j|}2. \]We count the number of pairs $(p, q, r)$ such that student $i$ is in club $j$ with society $k$. Condition ii) and iii) together tell us that each club $C_m$ contributes $|C_m|(2|C_m|+1)$ to this number. By summing this across all clubs, we obtain \[\sum \dbinom{|C_j|}2 = 10001k \]. This implies that $k = 5000$, and a construction is to let all students be in $1$ club with $5000$ societies.

This problem made me so mad. Number the clubs $1,2, \ldots, \ell$. Let $s_i$ and $t_i$ denote the number of students in the $i$'th club. Now, we will do the following genius calculations \[ 10001k = \sum s_it_i = \sum s_i \left ( \frac{s_i-1}{2} \right ) = \sum \binom{s_i}{2} = \binom{10001}{2} \implies k = 5000\]Construction for $k=5000$ is just one club with every student and part of $5000$ societies.

Let there be $n$ clubs such that the $i$th club has $2s_i+1$ members. We see that $\sum \dbinom{2s_i+1}2 = \dbinom{10001}2$ by the first condition. Consider the sum of the number of people across all societies. By the second condition, this is $10001k$ but by the third condition, this is also $\sum s_i(2s_i+1) = \sum \dbinom{2s_i+1}2 = \dbinom{10001}2$. Then it follows that $k=5000$.

bruh this one is so weird to wrap your mind around even though its standard double counting: Notice that the number of pairs of students =10001 choose 2 are equal to choosing any club and taking two students, since those two students are only in this single club together, so we sum over all clubs=sum over 2m+1 choose 2=sum over m(2m+1). On the other hand, this is also equivalent to choosing a student and a society because any student-society makes up a distinct club in m(2m+1) ways. Hence 10001C2=2m+1C2=10001k, which readily implies k=5000! $\blacksquare$

Consider the set $\mathcal{A}=\{ (s , C , S_{0}) | s \in C , C \in S_{0}, s \text{ is a student } , C \text{ is a club, and } S_{0} \text{ is a society.} \}$ So since for each student and each society, the student is exactly in one club of the society we have $|\mathcal{A}|=10001k$. Also consider a particular club $C_{i}$ , denote $|C_{i}|$ as number of students in it. So we have $|C_{i}|$ many students in a particular club $C_{i}$ , now there are $\frac{|C_{i}|-1}{2}$ societies. consider total such clubs to be be $n$ we have $\sum_{i=1}^{i=n} |C_{i}|\cdot \left(\frac{|C_{i}|-1}{2}\right)=|\mathcal{A}|$ Also, Notice for all clubs we have total pair of distinct students to be $\sum_{i=1}^{i=n} \binom{|C_{i}|}{2}$ and also clearly from $(i)$ there is exactly one club for which two distinct pair of students are in a club so we have $\binom{10001}{2}=\sum_{i=1}^{i=n} \binom{|C_{i}|}{2}$ so we have $10001k=\binom{10001}{2} \implies \boxed{k=5000}$. $\blacksquare$ edit: 850th post to this cool problem!

Let there be $n$ clubs, with the $i$th club having $a_i$ members. Then from the first condition, it must be that \[ \binom{a_1}{2} + \binom{a_2}{2} + \dots + \binom{a_n}{2} = \binom{10001}{2} \]But the second and third condition imply that \[ \binom{a_1}{2} + \binom{a_2}{2} + \dots + \binom{a_n}{2} = 10001k \]It immediately follows that $k = \boxed{5000}$. $\blacksquare$

Label the clubs $C_i$ and the societies $S_i$, with corresponding member counts $c_i$ and $s_i$. The first condition tells us the total number of pairings is \[\binom{10001}{2} = \sum \binom{c_i}{2}.\]The second and third conditions give us the total sum of member counts across all societies as \[10001k = \sum s_i = \sum \frac{c_i-1}{2} \cdot c_i = \sum \binom{c_i}{2}.\] Equating these, we find $k=\boxed{5000}$. $\blacksquare$

Let the clubs be $C_1, C_2, \ldots, C_j$, with club $C_i$ having $x_i$ members for some odd $x_i$. Then by the first condition, we have $$\binom{10001}{2} = \sum_{i = 1}^j \binom{x_i}{2}.$$By the second condition, we have $$10001k = \sum_{i = 1}^j x_i \cdot \frac{x_i - 1}{2} = \sum_{i = 1}^j \binom{x_i}{2},$$by considering the sum of the number of members across all $k$ clubs. Therefore $k = \tfrac{10000}{2} = 5000$. For a construction, take one and only one club which has all $10001$ students and is in $5000$ societies.

Suppose there are $n$ clubs, each with $2m_1+1,2m_2+1,\dots$ members. Notice that there are $\binom{10001}2$ pairs of students. However, there are also \[\sum\binom{2m+1}2\text{ pairs}\]as well. Thus, \[\sum\binom{2m+1}2=\binom{10001}2.\]In addition, for each society, they have $10001$ students summed over each club in the society. Thus, there are $10001k$ student-society relationships. Through clubs, there are also a total of $\sum(2m+1)m$ student-society relationships. Thus \[10001k=\sum(2m+1)m.\]Notice that $\sum(2m+1)m=\sum\binom{2m+1}2$. Thus, \[10001k=\binom{10001}2.\]Thus, $k=5000$. We may construct this as exactly $1$ club in a total of $5000$ societies, with this club containing all students.

Let us denote the set of clubs as $C$, and denote the number of members the $i$th club has as $2m_i+1$. Then from condition one we get that $$\binom{10001}{2}=\sum_{i=1}^{|C|}\binom{2m_i+1}{2}$$ Then from condition two we know that the total number of times every student appears in a society is $10001k$ counting from the perspective of students. From condition three we can count the same thing from the perspective of the clubs which is $\sum_{i=1}^{|C|}(2m_i+1)m_i$. Thus $$10001k=\sum_{i=1}^{|C|}(2m_i+1)m_i$$ But note that $$\binom{10001}{2}=\sum_{i=1}^{|C|}\binom{2m_i+1}{2}\implies 10001(5000)=\sum_{i=1}^{|C|}(2m_i+1)m_i$$ Thus we get $10001k=10001(5000) \implies k=5000$

Gsolved w acklew We begin by rephrasing the problem: Quote: There are $10001$ beta males at an university. Some beta males join together to form several sigma societies (a beta male may belong to different sigma societies). Some sigma societies join together to form several alpha assemblies (a sigma society may belong to different alpha assemblies). There are a total of $\alpha$ alpha assemblies. Suppose that the following conditions hold: i.) Each pair of beta males are in exactly one sigma society. ii.) For each beta male and each alpha assembly, the beta male is in exactly one sigma society of the alpha assembly. iii.) Each sigma society has an odd number of beta males. In addition, a sigma society with ${2m+1}$ beta males ($m$ is a positive integer) is in exactly $m$ alpha assemblies. Find all possible values of $\alpha$. Condition $(i)$ tells us that the number of pairs of beta males is equal to $\sum \binom{\sigma_i}{2}$ where $\sigma_i$ is the number of students within sigma society $i$. Notice that this is also just equal to $\binom{10001}{2}$. Condition $(ii)$ tells us that each alpha assembly contains exactly $1$ copy of each beta male. Also implying that there are a total of $10001\alpha$ total beta males (counting duplicates). Condition $(iii)$ tells us that the number of ways to choose $2$ beta males within a sigma society is equal to the number of ways to choose a singular beta male in a sigma society, and the number of alpha assemblies which that sigma society is a part of. This is true as $\binom{2m+1}{2} = (2m+1)m$. If we sum over all sigma societies, we get that the first part is equal to our value from condition $(i)$ which is equal to $\binom{10001}{2}$. We also get that the second part $(2m+1)m$ when summed over all sigma societies is equal to the total number of beta males over all alpha assemblies as it counts every instance of every beta male in each alpha assembly. From condition $(ii)$ this value is equal to $10001\alpha$. Putting this all together gives \[ \binom{10001}{2} = \sum_{\sigma\text{ soc.}} \binom{2m+1}{2} = \sum_{\sigma\text{ soc.}}(2m+1)m = 10001\alpha\\ \implies \alpha=5000 \] This is achievable if we set the number of sigma societies to $1$.

thoomgus wrote: Gsolved w acklew

Who are you?

We will count the number of triples $(s \to C \to S)$ where $s$ is a student who belongs to club $C$ which belongs to society $S$. Call such triples valid. Suppose there are $t$ clubs, and denote $2m_i + 1$ as the number of people in club $1 \le i \le t$. The first condition tells us there is a 1-to-1 correspondence between pairs of students and pairs of students in each club, implying that $$\sum_{i = 1}^t \binom{2m_i + 1}{2} = \binom{10001}{2}.$$The second condition tells us that given any values of $s$ and $S$, there exists a unique value of $C$ in a valid triple. So there are $10001k$ valid triples. On the other hand, the third condition tells us that for every $i$, if we let $C$ be club $i$ there are $2m_i + 1$ values for $s$ and $m_i$ values for $S$ to form a valid triple. Altogether we have $$10001k = \sum_{i = 1}^t m_i(2m_i + 1) = \sum_{i = 1}^t \binom{2m_i + 1}{2} = \binom{10001}{2} = 10001 \cdot 5000$$so $k = 5000$. As a construction, suppose there is $1$ club with all $10001$ students, and $5000$ societies each containing $1$ club.

Let $p,c,s$ denote a student, club and society respectively. Let $(p,c)$ be $1$ if $p\in c$ and $0$ otherwise. Similarly, let $(c,s)$ be $1$ if $c\in s$ and $0$ otherwise. Also, let $|c|$ denote number of students in $c$. The given criteria are equivalent to: $$\sum_p 1=10001$$$$\sum_c(p,c)(p',c)=1, p\neq p'$$$$\sum_c (p,c)(c,s)=1$$$$\sum_s (c,s)=\frac{|c|-1}{2}$$ Now we need to manipulate the expressions to get $k$: $$k=\sum_s 1=\sum_s \sum_c (p,c)(c,s)=\sum_c (p,c) \frac{|c|-1}{2}$$$$\sum_{p, p'\neq p}1=10001000=\sum_{p,p'}\sum_c (p,c)(p',c)=\sum_c \sum_p (p,c) \sum_{p'\neq} (p',c)=\sum_p \sum_c |c|-1=2\cdot 10001 k$$ Therefore $k=5000$. This is possible when there is $1$ club and $5000$ societies. NT functions flashbacks anyone?

The answer is only $k = 5000$. Claim: $k = 5000$ is possible. Proof. We do the stupidest thing possible: put all $10001$ students in one club, then put this club in $5000$ different societies. This trivially satisfies all of the conditions. $\square$ Claim: $k = 5000$ is necessary. Proof. Let $A$, $B$, and $C$ denote the set of students, clubs, and societies, respectively. We double count the number of triples $(a, b, c) \in A \times B \times C$ for which $a \in b \in c$. Call such a triple orderly. By the second condition, for each pair $(a, c) \in A \times C$ there is exactly one club $b \in B$ which can be added to form an orderly triple $(a, b, c)$. Counting this way gives a total of $|A| \times |C| = 10001k$. On the other hand, the number of orderly triples is just $\sum_{c \in C} \sum_{b \in c} |b|$. So it's convenient to evaluate this sum by counting over all clubs, since a club with $2m + 1$ students is counted $m$ times. Thus we need to evaluate \[\sum_{|b| = 2m + 1} m(2m + 1) = \sum_{|b| = n} \binom{n}{2},\]which by the first condition is just $\binom{10001}{2} = 5000 \cdot 10001$. Comparing this with the first count yields $k = 5000$ as desired. $\square$

Note that $\sum m(2m + 1)$ over all clubs is equal to the number of pairs of students who are in the same club, counted once for each club, which is just the total number pairs of students, but that expression is also equal to the number of pairs of students and societies where the student is in a club of the society, which is just the total number of pairs of students and societies, giving $\binom{10001}{2} = 10001k$, giving $k = 5000$. We also have to show $k = 5000$ is possible, which is trivial by putting all the students in one club, which is under all $5000$ societies.

Let $c$ be the number of clubs, $2a_1 + 1$ be the number of students in Club $1$, $2a_2 + 1$ be the number of students in Club 2, and so on. We first count the number of triplets $(\text{student}, \text{club}, \text{student})$. Fix the two students, clearly there are $10001 \choose 2$ such triplets. When we fix a club, there are: $${10,001 \choose 2} = {2a_1 + 1 \choose 2} + {2a_2 + 1 \choose 2} + \dots + {2a_c + 1 \choose 2}$$ Now, we count the number of triplets $(\text{student}, \text{club}, \text{society})$, where a student belongs to the club and a club belongs to the society. Fix the student and a society, we have $10,001k$ such triplets. Fix a club, we have: $$10,001k = (2a_1 + 1)a_1 + (2a_2 + 1)a_2 + \dots + (2a_c + 1)a_c$$Simply solving the two equations, we have $k = 5000$.

Let $2c_i + 1$ denote the number of members of club $C_i$, and let there be $n$ clubs. Since there are ${10001 \choose 2}$ pairs of students, and each club has ${2c+ 1 \choose 2}$ pairs of students, we get \[\sum_{i = 1}^n {2c_i + 1 \choose 2} = {10001 \choose 2}\]Now, since there are $k$ societies, and each student appears exactly one in every society, there are $10001k$ people over all societies. Additionally, club $C_i$ appears in $c_i$ societies, therefore we have \[\sum_{i = 1}^n (2c_i + 1)c_i = 10001k\]Putting the above two equations together, we get \[10001k = \sum_{i = 1}^n (2c_i + 1)c_i =\sum_{i = 1}^n {2c_i + 1 \choose 2} = 10001 \cdot 5000 \]so $k = 5000$ is the only possible $k$. To show this works, consider a single club with everyone which is part of $5000$ committees with only that club. Clearly, every pair appears exactly once in all the clubs, there is exactly one student in each society, and any club with $2m+1$ members is in $m$ societies, so we are done.

Say there are $n$ clubs numbered from $1$ to $n$ and each club $i$ has $2c_i+1$ members. Then if we double count pair of students, by condition (i), we get that \[\sum_{i = 1}^n {2c_i + 1 \choose 2} = {10001 \choose 2}\]If we double count triples $(\text{Student}, \text{Club}, \text{Society})$ where the student is in the club and the club is in the society, we get from condition (ii) and (iii) that \[10001k=\sum_{i=1}^n c_i(2c_i+1)\]Combining the two, we get that the only value that works is $k=5000$, achieved by taking only one club containing everyone that there is and putting that club in $5000$ societies, which clearly works.