In a classroom with 5 students, is it possible to form 6 distinct groups such that every two groups share exactly 1 student?

Question

amistre64 · Answer

dunno if im reading the question correctly but

does  5 choose n = 6  have a solution?

amistre64 · Answer

what does it mean by 6 distinct groups?

amistre64 · Answer

5 choose 3 forms 10 groups

abcde

abc
abd
abe
acd
ace

ade
bcd
bce
bde
cde

 also 5 choose 4 gets us 10 groups

so i spose it possible to get 6 groups, just need to determine if they fit the rest of the requirements

btaylor · Answer

Given hint:
Suppose you could. Let $v_1,v_2,\dots,v_6$ be vectors in $\mathbb{R}^5$ such that $v_i$ is a vector whose entries consist of 0's and 1's as to encode the $i$-th club membership: the $j$-th component of $v_i$ is 1 if student $j$ is in the $i$-th club, and 0 otherwise. What does then the dot product $v_i \cdot v_j$, for $i \neq j$, represent? Use that to sow that $v_1,v_2,\dots,v_6$ must be linear independent vectors in $\mathbb{R}^5$  (which cannot possibly happen!) as follows: if $c_1v_1+c_2v_2+\dots + c_6v_6=0$, try expanding $$\left(c_1v_1+c_2v_2+\dots + c_6v_6\right) \cdot \left(c_1v_1+c_2v_2+\dots + c_6v_6\right) = 0$$ and conclude that $c_1=c_2=\dots=c_6=0$. Make sure to use the fact that $c_1^2+c_2^2+ \dots + c_6^2 + 2\left( c_1c_2+c_1c_3+c_1c_4+\dots+c_5c_6\right)=\left(c_1+c_2+\dots+c_6\right)^2 $ and that $\left| \left| v_i \right| \right|^2 \ge 1$.

btaylor · Answer

@amistre64 I think the question is asking if, out of a set of 5 students, you can form 6 groups (of any size, though I'm pretty sure it has to be at least 2) where every set of 2 groups only shares one person.

btaylor · Answer

@mathmale @ganeshie8 I think you'll enjoy this problem

amistre64 · Answer

so you spose we can have like:

ab  and  bcd  as elements to choose from, as opposed to just groups of 2 or 3 or 4 etc

btaylor · Answer

Yes. There are no given limits on the size of the groups.

amistre64 · Answer

beyond the scope of my ken at the moment ... reality is setting in :)

anonymous · Answer

yes

perl · Answer

nice problem

gorv · Answer

well my view is it is not possible with the only 5 student sharing exactly one sharing