Anyone know how to answer/attempt this question?

There are $n \geq 2 $ sets each containing 10 elements each. Any 2 sets contain 1 element in common and each 2 elements are only in the same set once.

Prove all elements occur in the same number of distinct sets.

Clarified in the comments: "each 2 elements are only in the same set once" means that if we pick any two elements, they will be found together in the same set exactly once, although each element separately could occur in multiple sets.

  • 1
    $\begingroup$ @Herstein Is it possible for two elements to never occur together in any set? $\endgroup$ – 6005 Aug 22 '16 at 9:27
  • $\begingroup$ Still not clear. As @6005 mentions. I think each pair of two elements has to occur exactly in one set. Otherwise there are counter-examples. $\endgroup$ – iamvegan Aug 22 '16 at 9:29
  • $\begingroup$ @6005 I don't think think so- I think all elements must be in exactly 1 set together. $\endgroup$ – Evgeny T Aug 22 '16 at 9:31
  • $\begingroup$ @Herstein OK, thanks. $\endgroup$ – 6005 Aug 22 '16 at 9:31
  • $\begingroup$ We don't know how many elements we have in total, right? $\endgroup$ – iamvegan Aug 22 '16 at 9:32

Let the collection of sets be $\mathcal{A} = \{A_1, A_2, A_3, \ldots, A_n\}$. Let $X = \cup \mathcal{A}$ be the universe of elements.

For $x,y \in X$, let $k_x$ be the number of sets in $\mathcal{A}$ that contain $x$, and let $k_{x,y}$ be the number of sets in $\mathcal{A}$ that contain $x$ and $y$. Then we have $$ 9k_x = \sum_{y \ne x} k_{x,y}, $$ because both sides count the number of pairs $(A, y)$, where $y \ne x$, $A \in \mathcal{A}$, and $x,y \in A$.

But we are also given that there is a unique set containing $x$ and $y$, so $k_{x,y} = 1$ for all $x,y \in X$. Therefore $$ k_x = \frac{\sum_{y \ne x} 1}{9} = \frac{|X| - 1}{9}. $$

In particular, the number of sets containing an element $x \in X$ (i.e. $k_x$) is the same for all $x$.

| cite | improve this answer | |
  • $\begingroup$ @bof What is the difference between "all elements" and "all elements in $X$" for you? $\endgroup$ – Darío G Aug 22 '16 at 9:47
  • $\begingroup$ Whatever. By the way, instead of proving that $k_x$ is constant, you might as well have proved that $k_x=10.$ $\endgroup$ – bof Aug 22 '16 at 10:49
  • $\begingroup$ @bof Thanks for pointing that out. +1 to your answer showing that and the reference to finite protective planes. Of course i didn't use the assumption $n \ge 2$ and this proves $k_x$ is still constant even if $n = 1$ $\endgroup$ – 6005 Aug 22 '16 at 17:01
  • $\begingroup$ Thank you. Of course the fact that $k_x$ is constant if $n=1$ hardly needs proof. $\endgroup$ – bof Aug 22 '16 at 20:56

Let $L$ be a collection of $10$-element subsets of a set $P.$ Let's call the elements of $P$ "points" and the elements of $L$ "lines". Assuming that (1) there are at least two lines, (2) any two distinct lines intersect in exactly one point, and (3) there is exactly one line containing any two distinct points, I will show that each point belongs to exactly $10$ lines.

Let $p$ be any point. Choose a line $X$ which does not contain $p.$

(How do we know such a line exists? By hypothesis there are two distinct lines, call them $Y$ and $Z.$ If $x\notin Y$ or $x\notin Z,$ we're done. If $x\in Y\cap Z,$ choose points $y\in Y\setminus\{p\}$ and $z\in Z\setminus\{p\};$ then the line $X$ containing $y$ and $z$ can't contain $p.$)

Let $X=\{x_0,x_1,\dots,x_9\}.$ Let $Y_i$ be the unique line containing $p$ and $x_i.$ Since every line through $p$ meets $X$ in exactly one point, the lines $Y_0,\dots,Y_9$ are distinct and they are all the lines through the point $p.$

P.S. The structure we're talking about is called a projective plane of order $9;$ it has $9^2+9+1=91$ points and $91$ lines; there are $10$ points on each line and $10$ lines through each point.

| cite | improve this answer | |

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.