Let $A$ be a set with $|A|=225$, meaning that $A$ has 225 elements. Suppose further that there are eleven subsets $A_1, \ldots, A_{11}$ of $A$ such that $|A_i|=45$ for $1\leq i\leq11$ and $|A_i\cap A_j|=9$ for $1\leq i<j\leq11$. Prove that $|A_1\cup A_2\cup\ldots\cup A_{11}|\geq 165$, and give an example for which equality holds.
Problem
Source:
Tags: USA(J)MO, USAMO, linear algebra, matrix, inequalities, function, Hi
29.04.2011 01:34
Can someone post a solution?
29.04.2011 01:36
I think I did something like this:
29.04.2011 01:36
29.04.2011 01:37
29.04.2011 01:45
Here's what I did:
The 225-element thing was irrelevant >_> But argh, QM-AM. I had no idea about that, I kind of brute-forced my way through it.
29.04.2011 03:27
29.04.2011 03:36
Mewto55555 wrote:
That's the kind of thing I was going for, but I didn't phrase it nearly as well. Did you get the example of equality holding? It's really nice.
29.04.2011 04:04
Yeah, from the solution above you have all but $x_2,x_3$ are necessarily 0 for equality, then solving the system gives $x_2=0, x_3=165$, so you just sort the 165 combinations of 3 subsets in some order and assign the nth element of A to the 3 subsets in the nth combination. (if that makes sense)
29.04.2011 04:13
How many points do you think will be awarded for giving the example? I quickly noticed that 11 choose 3 was 165, so I used that to kind of guess the equality case, but I didn't have time to prove the inequality. 2 points?
29.04.2011 04:28
NuncChaos wrote: How many points do you think will be awarded for giving the example? I quickly noticed that 11 choose 3 was 165, so I used that to kind of guess the equality case, but I didn't have time to prove the inequality. 2 points? I'd think it's just 1, especially if you didn't justify how it was the equality case.
29.04.2011 04:30
I am surprised that no one chose to express her proof in the language of linear algebra. It helps to keep things standard and simple. Let $A$ be the matrix defined by $A_{ij} = 1$ if element $i \in A_j$ and $A_{ij} = 0$ otherwise. Let $k$ be the number of nonzero rows in $A$, and for any matrix $M$, let $[M]$ denote the sum of the entries of $M$. By the Cauchy-Schwarz inequality, $k \geq \frac{[A]^2}{[A^TA]} \geq \frac{(45*11)^2}{45*11+9*110}=165$. The construction is trivial. The problems this year seemed to prefer mastery of fundamental skills to traditional ingenuity. That might have made things a bit tricky for rookies, but for veterans there really can be no excuse for not having solved most (all?) of the problems.
29.04.2011 06:11
Notice that USAMO 2001.1 is basically solved by the same method. It might be a bit harder than USAMO 2011.6, though.
21.07.2014 21:57
So I just got around to doing this on a train ride today. I thought I was misreading the problem and/or brain-dead, but indeed, the $225$ is actually totally, completely, unbelievably useless: if there are things in $A$ not in $\bigcup A_i$ then you just throw all of them away. And it's obviously useless. What. T____T
22.07.2014 17:12
This problem is probably over my head but can somebody please explain their solution in words if that makes sense. All the notation is messing with me and I don't really follow any of the posted solutions because I can't wrap my head around what they're saying.
22.07.2014 23:24
Basically:
06.08.2014 21:45
In fact, the official solution used the $225$ property. Here it is (copyright Committee on the American Mathematical Competitions):
Note that they really dance around the issue of the $60$ extra elements; they treat them as equal in stature to everything else, but they really ignore them.
08.08.2014 19:22
tenniskidperson3 wrote: In fact, the official solution used the $225$ property. ... Note that they really dance around the issue of the $60$ extra elements; they treat them as equal in stature to everything else, but they really ignore them. I don't think it's fair to say they "used" it, modulo specifying how many extra (useless) elements to throw in. If you replace $60$ with $M$ and $225$ with $165 + M$ everywhere, then the proof is exactly the same everywhere. In fact taking the compliment in $A$ was a totally lame useless move that didn't actually do anything. In fact, if you look at the line \[ |S|\leq 225-\frac{2}{3}\cdot11\cdot45+\frac{1}{3}\cdot\binom{11}{2}\cdot5=60, \] then you'll notice that the $60$ and $225$ are just to try and look cool, and the only relevant part of the calculation is their difference of $165$.
08.08.2014 19:35
Well, yeah. But what I meant was that they didn't automatically forget about the 60 extra elements. It made me think that CAMC believed that it was a special property of $225$ and $60$, or that they are just trying to push that onto everyone else. Of course any solution cannot rely on $225$ because the entire problem relies on $165$ special elements, and the other ones are forgotten. But their solution came the closest to making a neophyte believe that $225$ was important. Also, while taking the "compliment [sic]" unnecessarily introduced the universe these elements lived in, I don't think it's fair to say it was useless. It made the inequality they used work out; otherwise, (and since they never introduced exactly what $\ell(n)$ was, I'm still not totally sure) you'd have an uglier $1-\left(1-\frac{\ell}{2}\right)\left(1-\frac{\ell}{3}\right)$ instead of the nicer product.
08.08.2014 19:48
OK, that's fair. I would be surprised if the solution author actually thought that $60$ and $225$ had any special properties though. Good point about the $1 - \left(1 - \frac 12 \ell \right)\left( 1 - \frac 13 \ell \right)$ though, I hadn't thought of that.
04.07.2015 07:23
Combo Wominatoric said to use carrot like /\. The top of carrot is one of points in union, and the 2 bottoms are one of the 11 set. Let $n$ be union size. Next we double count. Let $d_i$ is the number of edge an elment belonged to. Obvious $\sum d_i=495$ since number of intersect is easy to say $9\times \binom{11}{2}$. Counting from the top of carrot it is $\sum \binom{d_i}{2}=\frac{1}{2}\sum d_i^2-d_1=\frac{1}{2}\sum d_i^2-495 \ge \frac{1}{2}=\frac{495}{2}(495/n-1)$ by Cauchy . Now from bottons we got $495$ since $45\times 11$. Now $3 \ge 495/n$, and result follow, since double count give same answer. Equality hold when we have 165 element, and every element in 3 sets is one example. My question: Does $\binom{max(i)}{2}|A_i \cap A_j|=max(i)|a_i|$ must hold??? EDIT: whoops I'm asleep sir
04.07.2018 10:01
In fact weaker assumption $|A_i\cap A_j|\le9$ for $1\leq i<j\leq11$ is sufficient.
11.12.2018 09:21
Note that the existence of the set $A$ is superfluous. So we can completely ignore it. Now we'll prove a more general result, given below:- GENERALISATION: Let $A_1,A_2, \dots ,A_n$ be $n$ sets satisfying the following properties- $|A_i|=\binom{n-1}{2}$ for $1 \leq i \leq n$ $|A_i \cap A_j|=n-2$ for $1 \leq i<j \leq n$ Then prove that $|A_1 \cup A_2 \cup \dots \cup A_n| \geq \binom{n}{3}$, and give an example for which equality holds. (The given problem asks to prove this result when $n=11$) PROOF: Let $A_1 \cup A_2 \cup \dots \cup A_n=X=\{a_1,a_2, \dots ,a_m\}$. Then we wish to prove that $m \geq \binom{n}{3}$. Consider a $n \times m$ chessboard, with the $n$ rows representing $A_1,A_2, \dots ,A_n$ and the $m$ columns representing the $m$ elements of $X$. On each square of the board, we write either zero or one, according to the following criterion - $1$ is written on the intersection of the $i^{th}$ row and the $j^{th}$ column if and only if $a_j$ is present in $A_i$; otherwise $0$ is written. Let $r(i)$ and $c(j)$ denote the number of times $1$ appears in the $i^{th}$ row and the $j^{th}$ column respectively. According to the question, $r(1)=r(2)= \dots =r(n)=\binom{n-1}{2}$. But, as $\sum_{i=1}^n r(i)=\sum_{j=1}^m c(j)$ represents the total number of times that $1$ appears in the board, we get that $$\sum_{j=1}^m c(j)=n \cdot \binom{n-1}{2}=3 \cdot \binom{n}{3}$$ Now, Let $T$ represent the total number of ways in which we can choose an unordered triplet $\{a_i,A_j,A_k\}$ such that $a_i \in A_j$ and $a_i \in A_k$. Then we can find $T$ in two ways - either by first selecting an element from the set $X$ and then finding pairs of sets in which it is present; or by first choosing two sets from the given $n$ sets and then multiplying by the total number of elements common between them. Equating the number of ways we get from these two methods, we have $$ \sum_{i=1}^m \binom{c(i)}{2}=\binom{n}{2} \times (n-2) $$$$ \Rightarrow \frac{1}{2}\left(\sum_{i=1}^m c(i)^2-\sum_{i=1}^m c(i) \right)=3 \cdot \binom{n}{3} $$$$ \Rightarrow \sum_{i=1}^m c(i)^2=6 \cdot \binom{n}{3}+3 \cdot \binom{n}{3}=9 \cdot \binom{n}{3} $$ Now, by Titu's Lemma, we get that $$\sum_{i=1}^m c(i)^2 \geq \frac{\left(\sum_{i=1}^m c(i) \right)^2}{m} \Rightarrow 9 \cdot \binom{n}{3} \geq \frac{\left (3 \cdot \binom{n}{3} \right)^2}{m} \Rightarrow m \geq \binom{n}{3}$$ Equality holds when $c(1)=c(2)= \dots =c(m)=3$ and $m=\binom{n}{3}$. One can easily find a construction now (My construction involves intersections of lines).
01.04.2019 03:16
First we will show the equality is achieveable. Let $A=A_1\cup \ldots \cup A_{11}$, so that $|A|=165$. If each of these $165$ elements are in $3$ subsets, we are done. Place one element in each of the $3$ subsets $A_i,A_j,A_k$, where $i<j<k$. Since $\tbinom{11}{3}=165$, this works. Let $S=\{ (A_i,A_j,x) \mid x\in A_i, x\in A_j\}$, and $T=|S|$. Since $|A_i \cap A_j|=9$, we know $T=9\tbinom{11}{2}=495$. Choose some element $d$. Let there be $y_d$ sets which include $d$. Then the number of pairs of sets which both include $d$ is $\tbinom{y_d}{2}$. Let $|A_1\cup \ldots \cup A_{11}|=n$, namely the number of elements which are in at least one set. Summing over all these elements, we get \[ T=\binom{y_1}{2}+\cdots+\binom{y_n}{2},\]where we have arbitrarily named the $n$ elements that are in at least one set as $1,\ldots,n$. By Jensen, \[ T=\binom{y_1}{2}+\cdots+\binom{y_n}{2} \ge n\binom{\frac{y_1+\cdots+y_n}{n}}{2}.\]Consider the sum of the number of elements in each of the $11$ subsets. This is $y_1+\cdots+y_n$, which we see by fixing an element and counting how many sets it is in. However, it is also $45\cdot 11=495$ since each subset has $45$ elements. Hence, \[ 495=T\ge n\binom{\frac{y_1+\cdots+y_n}{n}}{2} = n\binom{495/n}{2}.\]Then, \begin{align*} n\binom{495/n}{2} \le 495 &\implies \frac{n(495/n)(495/n-1)}{2} \le 495 \\ &\implies 495/n-1 \le 2 \\ &\implies n \ge 165. \end{align*}
04.01.2020 02:10
The problem is immeadiatelly solved by the Chung-Erdös inequality (sometimes known as the Erdös-Renyi inequality) by choosing the events in the most obvious way. In fact, many of the solutions of the thread seem to immediatelly generalize to the Chung-Erdös inequality. I think the following proof gives a fairly clear proof of the inequality assuming a suitable background with probabilities. Let $1_{S}$ be the indicator function of $S$ and let $X$ be the random variable $1_{A_1} + 1_{A_2} + \ldots + 1_{A_n}$. We have, by Cauchy-Schwarz that \begin{align*} \mathbb{E}(X^2) \ge \mathbb{E}(X)^2. \end{align*}This implies the key inequality \begin{align*} \mathbb{E}(X^2 | 1_{\bigcup A_i} = 1) \ge \mathbb{E}(X | 1_{\bigcup A_i} = 1)^2, \end{align*}so that, in more elementary terms, \begin{align*} \frac{\sum_{i, j} \Pr(A_i \cap A_j)}{\Pr\left(\bigcup A_i \right)} \ge \left(\frac{\sum_{i} \Pr(A_i)}{\Pr(\left(\bigcup A_i\right)}\right)^2. \end{align*}This rearranges to the Chung-Erdös inequality.
17.03.2020 05:41
Let $e_1, e_2, ..., e_n$ be the elements which are in one of more of the $A_i$, and for all $i$, let $e_i$ be in $x_i$ of the sets $A_1, A_2, ..., A_{11}$. We desire to prove $n\ge 165$. Note that we have $\sum x_i=|A_1|+...+|A_{11}|=495$, because in $|A_1|+...+|A_{11}|$, $e_i$ is counted $x_i$ times. Next, note that $\sum {x_i\choose 2}=\sum_{i<j} |A_i\cap A_j|={11\choose 2}\cdot 9=495$, because we are counting the number of ways to choose an element common to a pair of subsets. We can now find $\sum_{i=1}^n x_i^2=1485$ and $\sum_{i=1}^n=495$, so by Cauchy, $(x_1^2+...+x_n^2)(1+...+1)\ge (x_1+...+x_n)^2$. Thus, we have $1485\cdot n\ge 495^2$, meaning $n\ge 165$. Example of equality: Start with all 11 subsets empty. For each of the ${11\choose 3}=165$ unordered triples of distinct subsets, add an element which belongs to the three subsets in that triple and only the three subsets in that triple. It is easy to see that this works. $\blacksquare$
29.03.2020 22:00
what the heck
oops same as evan's solution posting for ref
21.04.2020 23:38
05.05.2020 00:50
WLOG set $S = \bigcup\limits_{i=1}^{11} A_{i} = \{1, 2, \dots k \}.$ Equality occurs when $A_i \cup A_j \cup A_k = \ell,$ where the choice of $\ell$ is dependent upon the sets chosen (i.e, $\ell$ cannot be common to more than $1$ such set intersection.) This will account for ${11 \choose 3} = 165$ elements in set $S.$ Let $x_i$ denote the number of sets that element $i$ is in. From double counting, we arrive at \begin{align*} \sum_{i = 1}^{k} x_{i} = 45 \cdot 11 = 495 \\ \sum_{i =1}^{k} {x_i \choose 2} = \sum_{1 \le i < j \le 11} | A_i \cap A_j | = 9 \cdot {11 \choose 2} = 495 \\ \end{align*} Thus, it follows that $\sum_{i = 1}^k x_i = 495$ and $\sum_{i=1}^k x_i^2 = 495 \cdot 3.$ To finish, by QM-AM, $$\sqrt{\frac{x_1^2 + \dots x_k^2}{k}} \ge \frac{x_1 + \dots + x_k}{k},$$and we get $k \ge 165$ as requested. $\blacksquare$
22.09.2020 18:22
Disregard the condition $|A| = 225.$ Let $x = |A_1\cup A_2\cup\ldots\cup A_{11}|,$ and let $a_i$ be the number of times the element $i$ appears in over all $11$ subsets, for $1 \leq i \leq k.$ Equality holds when all $a_i = 3.$ Note $\sum_{i=1} ^k a_i = 45 \cdot 11 = 495,$ and $\sum_{i=1}^k a_i^2 = 2 \sum_{i=1}^k \binom{a_i}{2} + \sum_{i=1}^k a_i = 2 \cdot \binom{11}{2} \cdot 9 + 45 \cdot 11 = 3 \cdot 495.$ Now by Cauchy-Schwarz, we find $k \sum_{i=1}^k a_i^2 \geq \left(\sum_{i=1} ^k a_i \right)^2,$ thus $k \geq \frac{495}{3} = 165.$ Remarks: This solution is motivated by PIE. Also, I found the equality case after I solved the problem; not sure if its a great example of looking at equality cases?
22.11.2020 19:40
Personally really liked this problem. Let $a_i$ denote the number of elements in $i$ subsets. Then, since each subset $A_i$ has $45$ elements, then we have $\sum_{i=1}^{\infty}(ia_i) = 495$. Now for each pair of subsets, we have that if an element is in $i$ subsets, it is involved in $\binom{i}{2}$ pairs of subsets. Since for all $1 \le i < j \le 11$ we have that $|A_i \cap A_j| = 9$ and there are $9 \cdot \binom{11}{2} = 495$ ways to choose two subsets and an element in both, then we have also that $\sum_{i=1}^{\infty}(\binom{i}{2}a_i) = 495$ meaning that $$\sum_{i=1}^{\infty}(i^2a_i) = 2\sum_{i=1}^{\infty}\left(\binom{i}{2}a_i\right)+ \sum_{i=1}^{\infty}(ia_i)= 3 \cdot 495$$and now by Cauchy-Schwartz, we see that $$\left(\sum_{i=1}^{\infty}(a_i) \right)\left(\sum_{i=1}^{\infty}(i^2a_i)\right) \ge \left(\sum_{i=1}^{\infty}(ia_i)\right)^2 \to \sum_{i=1}^{\infty}(a_i) \cdot 495 \cdot 3 \ge 495^2$$which means that $\sum_{i=1}^{\infty}a_i \ge 165$ and we are done.
21.03.2021 05:51
what a meme. also more of a global problem than an equality one Let the elements be the counting numbers and let $a_i$ be the number of times $i$ appears in one of the sets. We get the expressions $\sum a_i=495$ and $\sum \binom{a_i}{2}=9\cdot\binom{11}{2}=495$. Sum expression 1 and twice of expression $2$ to get that $\sum a_i^2=1485$, and QM-AM gives that there are at least 165 terms. Equality holds when each number is in exactly one of the $\binom{11}{3}=165$ possible triples of sets.
15.07.2021 23:34
18.09.2021 21:07
This is just Corradi's Lemma. And for the construction part,we see that due to the Cauchy used in the proof of the lemma,we see that each element should go to 3 distinct subsets. Now as $\binom{11}{3}=165$, we pick any three diistinct subsets,and place an element in each of the three subsets. By easy counting ,we see that this works.
09.11.2021 21:07
First, we provide the equality case WLOG let the elements be $\{1,2,3,\cdots\}$ Consider $x_i$ to be the number of times the value i comes in the 11 subsets. We claim that equality holds when each $x_i=3$ Indeed, if we place all $x_i$ into 3 subsets each, there are $\tbinom{11}{3}=165$ elements required, each subset gets $\tbinom{10}{2}=45$ elements, and intersections between 2 subsets are $\tbinom{9}{1}= 9$ For the bound, we consider the same variables, and note that \[\sum x_i = 45 \cdot 11 = 495\]\[\sum \tbinom{x_i}{2} = \tbinom{11}{2} \cdot 9 = 495\]Thus, \[\sum x_i ^2 =495 \cdot 3 \] Now just applying Cauchy gives you the desired result!
07.04.2022 05:31
Bound: Let $A=\{a_1,a_2,\ldots,a_{225}\}$ and WLOG FTSOC\[A_1\cup A_2 \cup \ldots \cup A_{11}\subseteq \{a_1,a_2,\ldots, a_{164}\}\]Let $b_i$ be the number of times $a_i$ occurs in the eleven subsets. Clearly, $\sum_{i=1}^{164} b_i=495$. Also, we can consider all the $\binom{11}{2}=55$ sets $A_i\cap A_j$ for $i<j$. Each of these sets have $9$ elements. For a given $a_k$, if it is in $n$ of these sets, then $\binom{b_k}{2}=n$. So \[\sum_{i=1}^{164}\binom{b_i}{2}=55\cdot 9=495\] We can use $\binom{x}{2}=\frac{x(x-1)}{2}$, rearrange and get $\sum_{i=1}^{164}b_i^2=495\cdot 3=1485$. By Cauchy, we now have \[\sum_{i=1}^{164}1\cdot \sum_{i=1}^{164}b_i^2\ge \left(\sum_{i=1}^{164}b_i\right)^2,\]so $164\cdot 1485\ge 495^2=1485\cdot 165$, not true. $\blacksquare$ Construction: Set all the $b_i$ to $3$, where no two different $a_i$ are in the exact same three subsets (achievable since $\binom{11}{3}=165$). Note that each $A_i$ has $\binom{10}{2}=45$ elements and the intersection has $\binom{9}{1}=9$ elements. $\blacksquare$
19.12.2022 14:13
Special thanks to $|A| = 225$ for trolling me. We'll first prove the bound. Let $A = {a_{1}.......a_{225}}$. Let $x_{i} = $#times $a_{i}$ appeared in different subsets. Note that \[x_{1} \dots + x_{n} = 495\]\[\binom{x_{1}}{2} \dots + \binom{x_{n}}{2} = 495\]. which gives $\sum_{i = 1}^{n} x_{i}^{2} = 495\cdot3$. Now simple QM-AM proves the bound. The equality case is to put each $x_{i} = 3$, this gives total $\binom{11}{3} = 165$ elements in total, $\binom{10}{2} = 45$ elements in each subset & pairwise intersection of any two subsets to be $\binom{9}{1} = 9$. So, we're done.
21.12.2022 00:12
First, we prove the desired bound. Let $S = A_1 \cup A_2 \ldots \cup A_{11}$, and suppose FTSOC that $| S | = n < 165$. If the $n$ elements of $S$ appear in $x_1, x_2, \ldots, x_n$ of the $11$ subsets respectively, then $$\sum_{i = 1}^{n} x_i = 11 \cdot 45 = 495.$$Moreover, double counting with an incidence matrix between the $11$ subsets and each element $x_i$ yields $$495 = 9 \binom{11}{2} = \sum_{i = 1}^{n} \binom{x_i}{2} = \frac{1}{2} \left( \sum_{i = 1}^{n} x_i^2 - \sum_{j = 1}^{n} x_j \right)$$$$\ge \frac{1}{2} \left( \frac{1}{n} \left( \sum_{i = 1}^{n} x_i \right)^2 - 495 \right) > \frac{1}{2} \left( \frac{1}{165} \cdot 495^2 - 495 \right) = 495$$by Cauchy-Schwarz, which is absurd. Hence, we must have $n \ge 165$. Now, if $S = \{t_1, t_2, \ldots, t_{165} \}$, then we can just let each $t_k$ where $1 \le k \le 165$ belong to $3$ of the $11$ given subsets, as $\binom{11}{3} = 165$. This construction clearly works, so we're done. $\blacksquare$
02.07.2023 05:52
1. Construction (Upper Bound) First, we construct the equality case. This is easily doable by ensuring that for every $3$-set subset of the $11$ sets, there is exactly one mutual element between the three sets. This clearly works, as there will be $\binom{11}{3}=165$ elements in the union, $\binom{10}{2}=45$ elements per set, and $\binom{9}{1}=9$ elements in the intersection of any two of the sets. 2. Lower Bound FTSOC, assume that there are less than $165$ elements in the intersection. Let these elements be $e_1$, $e_2$, $\dots$, $e_k$, and for each integer $1\le{}i\le{}k$, let $e_i$ occur a total of $s_i$ times over all $11$ sets. We now have that \[s_1+s_2+\dots{}+s_k=11*45=495,\]by the $|A_i|=45$ condition, and \[\binom{s_1}{2}+\binom{s_2}{2}+\dots{}+\binom{s_1}{2}=9*\binom{11}{2}=495,\]by the $|A_i\cap{}A_j|=9$ condition. Note that if $k\leq{}164$, we have that by Jensen's Inequality and the first condition, \[\binom{s_1}{2}+\binom{s_2}{2}+\dots{}+\binom{s_1}{2}\geq{}161\binom{3}{2}+3\binom{4}{2}=501,\]a contradiction, since $495<501$. Therefore $k\geq{}165$, meaning that there are at least $165$ elements in the union, finishing the problem.
30.10.2023 01:29
Rephrase the problem as follows: We have a grid with 11 rows and some number of columns. In each row, 45 cells are shaded and the rest are blank. In each pair of rows, there are exactly 9 positions for which both rows have a shaded cell. Show that the minimum number of columns possible is 165. Double-count pairs of shaded cells in the same column. Clearly, this is equal to $9\cdot {11\choose 2}=495.$ Let $c$ be the number of columns. Then, the average number of shaded cells per column is $495/c$. Thus, by Jensen's inequality, $$495=\sum {shaded\choose 2}\geq c {495/c\choose 2}$$$$495\geq c(\frac{(495/c)(495/c-1)}{2})$$$$2\geq 495/c-1$$$$495/c\leq 3$$$$3c\geq 495$$$$c\geq 165,$$which shows the bound. Note that by our work above, we know that all columns must have $495/c$ cells for equality to hold, so each column has 3 cells. At this point, we note that $165={11\choose 3}$, so we construct as follows: have each possible column of 3 shaded cells out of 11 occur exactly once. Then, clearly by symmetry, given any two rows, the number of positions with both shaded cells is the same across all pairs of rows. Since each column contributes 3 to the sum of all such quantities, the total value is 495. Hence, the value for each pair of rows is $495/55=9$, and we are done.
26.12.2023 21:42
Define the function $f:A\longrightarrow \mathbb{N}_{\geq0}$ such that for each $x\in A$, $f(x)$ denotes the number of subsets $x$ belongs to, from $A_1,A_2,\ldots,A_{11}$. Consider the bipartite graph on $11+225$ vertices, with the first 11 vertices representing $A_1,A_2,\ldots,A_{11}$ and next 225 vertices representing the elements of $A$. A subset is connected to the element if the element lies in the subset. By definition, $f(x)$ is the corresponding degree of $x$ in the above graph and degree of the subsets is $45$ each. Suppose this graph has $S$ edges. Then, \[S=\sum_{x\in A}f(x)=11\times45=495\]Now, we calculate the number of ``angles" subtended by each pair of subsets on the set of elements in the graph. This means the number of connections $A_ixA_j$, which means that $x\in A_i$ and $x\in A_j$. Call this number $T$. Then, \[T={11\choose2}9=\sum_{x\in A}{f(x)\choose2}=495\]\[\Longrightarrow \sum_{x\in A} f(x)=495, \ \ \sum_{x\in A} f(x)^2=1485\]Suppose there are $N$ elements $x$ for which $f(x)>0$. From Cauchy-Schwarz Inequality, we have \[\left(\sum_{x\in A} f(x)^2\right)\left(N\right)\geq \left(\sum_{x\in A} f(x)\right)^2\Longrightarrow N\geq165,\]as claimed. Equality holds when $f(x)=3$ for all $165$ elements. This happens when each element is in exactly 3 subsets. For the equality, the elements of each subset are partitioned into 5 subsets, each of size $9$, and are each distributed to two of the rest of the subsets from $A_1,A_2,\ldots,A_{11}$.
18.01.2024 08:41
The hardest part is to realize $\binom{11}{3} = 165$. Let $n = |A_1 \cup A_2 \cup \dots \cup A_{11}|$ and for $1 \le i \le$, let $a_i$ be the number of times the element $i$ appears in over 11 subsets. Equality $|A_1 \cup A_2 \cup \dots \cup A_{11}| = 165$ occurs if all $a_i$'s are $3$. Now we'll prove that $|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165$. Note that double counting gives \begin{align*} \sum_{i=1}^{n} a_i = 45 \cdot 11 = 3 \cdot 165 \\ \sum_{i=1}^{n} \binom{a_i}{2} = 9 \cdot \binom{11}{2} = 3 \cdot 165 \end{align*} Hence $\sum_{i=1}^{n} a_i = \sum_{i=1}^{n} \binom{a_i}{2}$. Let $A = \{i \,|\, a_i \le 2\}, B = \{i \,|\, a_i = 3\}$, $C = \{i \,|\, a_i \ge 4\}$. Then we only need to prove that $|A| + |B| + |C| \ge 165$. Note that $3 \cdot 165 = \sum_{i\in A}a_i + \sum_{i\in B}a_i + \sum_{i\in C}a_i = 3 \cdot 165$, thus $\sum_{i\in A}a_i + \sum_{i\in C}a_i = 3 \cdot (165 - |B|)$. Therefore we only need to prove that $\sum_{i\in A}a_i + \sum_{i\in C}a_i \le 3(|A| + |C|)$. Note that $\sum_{i\in A}a_i \le 2|A|$, so it suffices to prove $\sum_{i\in C}a_i \le |A| + 3|C|$. Since $\sum_{i=1}^{n} \binom{a_i}{2} - a_i = 0$, so $\sum_{i\in A}-1 + \sum_{i\in C}\frac{a_i(a_i - 3)}{2} = 0$, in other words $|A| = \sum_{i\in C}\frac{a_i(a_i - 3)}{2}$. So $|A| + 3|C| = \sum_{i\in C}\frac{a_i(a_i - 3)}{2} + 3$ and for all $x \ge 4$, we have $\frac{x(x - 3)}{2} + 3 \ge x$, hence $\sum_{i\in C}\frac{a_i(a_i - 3)}{2} + 3 \ge \sum_{i\in C}a_i$, as required. $\blacksquare$
11.08.2024 20:37
Let $a_i$ be some element in $A$ and let $b_i$ be the number of times $a_i$ appears in $A_1, A_2, \dots, A_{11}$. We can double count $b_i$ as $\sum_i b_i = 45 \cdot 11$ from the first condition and $\sum_i \binom{b_i}{2} = 9 \cdot \binom{11}{2} = 495$ from the second. Then by Jensen's we get $\sum_{i=1}^k \binom{b_i}{2} = k\binom{\frac{b_1 + b_2 + \dots}{k}}{2} = k\binom{\frac{495}{k}}{2} \leq 495$ which implies that $\frac{495-k}{k} \leq 2$ so $k \geq 165$ as desired. Our equality case is to take $A_i$ as the set of all $3$ element subsets of $\{1, 2, \dots, 11\}$ containing $i$ which works as $\binom{11}{3} = 165$.
14.01.2025 15:42
Start by letting the union of $A_i$ the set $\{1,2,3,\cdot\cdot\cdot,n\}$ for some value of n. Consider the incidence matrix $M$ such as rows are $1$ up to $n$, and columns are pairs $(A_i,A_j)$ with a entry $M(e_i,A_i,A_j)=1$ iff $e_i\in A_i \cap A_j$. Let the number of $1$'s in this matrix $T$. By columns, $T=11\cdot 5\cdot 9$, by $|A_i \cap A_j|=9$ By rows, $T=\sum \frac{b_i(b_i-1)}{2} \geq n \frac{\frac{\sum b_i}{n}(\frac{\sum b_i}{n}-1)}{2}$ by Jensen where $b_i$ is the number of times $i$, thus $\sum b_i=11\cdot 45$ which the total number of elements in multiset union of $A_i$ ( just take the matrix with rows $1$ up to $n$ and columns $A_i$ and double count the total number of ones). Thus doing simplifications yields $n\geq 165$. Construction comes by equality case of jensen all $b_i=3$. posting for reference