Mixing
There are $n$ different 3-element subsets $A_1,A_2,…,A_n$ of the set $1,2,…,n$, with $|A_i cap A_j| not= 1$ for all $i not= j$.
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Determine all possible values of positive integer $n$, such that there are $n$ different 3-element subsets $A_1,A_2,...,A_n$ of the set $1,2,...,n$, with $|A_i cap A_j| not= 1$ for all $i not= j$.
Attempt:
It is quite clear that for $n=4k$ such a system exist. For $n=4$, we have $A_1 =1,2,3$, $A_2 =1,2,4$, $A_3 =2,3,4$, $A_4 =1,3,4$. It is not hard to see that induction $nto n+4$ works. Now I would like to prove that there is no such system if $4nmid n$.
I thought about linear algebra approach. Observe the given sets as vectors in $mathbbF_2^n$. Then since $A_icdot A_i =1$ and $A_icdot A_j = 0$ for each $ine j$ these vectors are linear independent:
$$ b_1A_1+b_2A_2+...+b_nA_n = 0;;;; /cdot A_i$$
$$ b_1cdot 0+b_2cdot 0+...+b_icdot 1+...b_ncdot 0 =0implies b_i=0$$
But now, I'm not sure what to do...
combinatorics contest-math algebraic-combinatorics
edited Jul 22 at 19:33
Batominovski
23.2k22777
asked Jul 22 at 18:53
greedoid
26.1k93473
add a comment |Â
up vote
3
down vote
favorite
Determine all possible values of positive integer $n$, such that there are $n$ different 3-element subsets $A_1,A_2,...,A_n$ of the set $1,2,...,n$, with $|A_i cap A_j| not= 1$ for all $i not= j$.
Attempt:
It is quite clear that for $n=4k$ such a system exist. For $n=4$, we have $A_1 =1,2,3$, $A_2 =1,2,4$, $A_3 =2,3,4$, $A_4 =1,3,4$. It is not hard to see that induction $nto n+4$ works. Now I would like to prove that there is no such system if $4nmid n$.
I thought about linear algebra approach. Observe the given sets as vectors in $mathbbF_2^n$. Then since $A_icdot A_i =1$ and $A_icdot A_j = 0$ for each $ine j$ these vectors are linear independent:
$$ b_1A_1+b_2A_2+...+b_nA_n = 0;;;; /cdot A_i$$
$$ b_1cdot 0+b_2cdot 0+...+b_icdot 1+...b_ncdot 0 =0implies b_i=0$$
But now, I'm not sure what to do...
combinatorics contest-math algebraic-combinatorics
edited Jul 22 at 19:33
Batominovski
23.2k22777
asked Jul 22 at 18:53
greedoid
26.1k93473
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Determine all possible values of positive integer $n$, such that there are $n$ different 3-element subsets $A_1,A_2,...,A_n$ of the set $1,2,...,n$, with $|A_i cap A_j| not= 1$ for all $i not= j$.
Attempt:
It is quite clear that for $n=4k$ such a system exist. For $n=4$, we have $A_1 =1,2,3$, $A_2 =1,2,4$, $A_3 =2,3,4$, $A_4 =1,3,4$. It is not hard to see that induction $nto n+4$ works. Now I would like to prove that there is no such system if $4nmid n$.
I thought about linear algebra approach. Observe the given sets as vectors in $mathbbF_2^n$. Then since $A_icdot A_i =1$ and $A_icdot A_j = 0$ for each $ine j$ these vectors are linear independent:
$$ b_1A_1+b_2A_2+...+b_nA_n = 0;;;; /cdot A_i$$
$$ b_1cdot 0+b_2cdot 0+...+b_icdot 1+...b_ncdot 0 =0implies b_i=0$$
But now, I'm not sure what to do...
combinatorics contest-math algebraic-combinatorics
edited Jul 22 at 19:33
Batominovski
23.2k22777
asked Jul 22 at 18:53
greedoid
26.1k93473
Determine all possible values of positive integer $n$, such that there are $n$ different 3-element subsets $A_1,A_2,...,A_n$ of the set $1,2,...,n$, with $|A_i cap A_j| not= 1$ for all $i not= j$.
Attempt:
It is quite clear that for $n=4k$ such a system exist. For $n=4$, we have $A_1 =1,2,3$, $A_2 =1,2,4$, $A_3 =2,3,4$, $A_4 =1,3,4$. It is not hard to see that induction $nto n+4$ works. Now I would like to prove that there is no such system if $4nmid n$.
I thought about linear algebra approach. Observe the given sets as vectors in $mathbbF_2^n$. Then since $A_icdot A_i =1$ and $A_icdot A_j = 0$ for each $ine j$ these vectors are linear independent:
$$ b_1A_1+b_2A_2+...+b_nA_n = 0;;;; /cdot A_i$$
$$ b_1cdot 0+b_2cdot 0+...+b_icdot 1+...b_ncdot 0 =0implies b_i=0$$
But now, I'm not sure what to do...
combinatorics contest-math algebraic-combinatorics
edited Jul 22 at 19:33
Batominovski
23.2k22777
asked Jul 22 at 18:53
greedoid
26.1k93473
edited Jul 22 at 19:33
Batominovski
23.2k22777
edited Jul 22 at 19:33
Batominovski
23.2k22777
edited Jul 22 at 19:33
Batominovski
23.2k22777
23.2k22777
asked Jul 22 at 18:53
greedoid
26.1k93473
asked Jul 22 at 18:53
greedoid
26.1k93473
asked Jul 22 at 18:53
greedoid
26.1k93473
26.1k93473
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
Suppose that there are $n$ such sets $A_1,A_2,ldots,A_n$, represented by indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_ninmathbbF_2^n$. Equip $mathbbF_2^n$ with the usual inner product $langle_,_rangle$.
We already know that the vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n$ are linearly independent. Therefore, they span $mathbbF_2^n$. Thus, the vector $boldsymbol1:=(1,1,ldots,1)$ can be written as
$$mathbfa_j_1+mathbfa_j_2+ldots+mathbfa_j_k$$
for some $j_1,j_2,ldots,j_kin1,2,ldots,n=:[n]$ with $j_1<j_2<ldots<j_k$. If $k<n$, then there exists $rin[n]$ such that $rneq j_mu$ for all $mu=1,2,ldots,k$. That is,
$$1=langle mathbfa_r,boldsymbol1rangle =sum_mu=1^k,langle mathbfa_j_mu,mathbfa_rrangle=0,,$$
which is a contradiction. Therefore, $k=n$, whence
$$boldsymbol1=sum_j=1^n,mathbfa_j,.tag*$$
Consequently, each element of $[n]$ belongs in an odd number of $A_1,A_2,ldots,A_n$, whence at least one of the sets $A_1,A_2,ldots,A_n$.
Furthermore, it is not difficult to show that every element of $[n]$ must belong in at least two of the $A_i$'s. (If there exists an element of $[n]$ belonging in exactly one $A_j$, then you can show that there are at most $n-2$ possible $A_i$'s.) Let $d_j$ be the number of sets $A_i$ such that $jin A_i$. Then
$$sum_j=1^n,d_j=3n,.tag#$$
Note that $d_jgeq 2$ for all $jin[n]$.
From (*), we conclude that $d_jgeq 3$ for every $jin[n]$. However, (#) implies that $d_j=3$ for all $jin[n]$; i.e., every element of $[n]$ must be in exactly three of the $A_i$'s. Write $mathbfe_1,mathbfe_2,ldots,mathbfe_n$ for the standard basis vectors of $mathbbF^n_2$. We see that
$$mathbfe_j=mathbfa_p+mathbfa_q+mathbfa_r$$
where $j$ is in $A_p$, $A_q$, and $A_r$. This shows that
$$A_p=j,x,y,,,,A_q=j,y,z,,text and A_r=j,z,x$$
for some $x,y,zin[n]$. Since $x$ already belongs in $A_p$ and $A_r$, it must be belong in another $A_s$. Clearly, $A_s$ must be equal to $x,y,z$. From here, we conclude that the four elements $j,x,y,z$ belong in exactly four of the $A_i$'s, which are $j,x,y,j,y,z,j,z,x,x,y,z$. The rest is easy.
answered Jul 22 at 19:21
Batominovski
23.2k22777
I read it all. All I have to check now why is $d_igeq 2$ for each $i$.
– greedoid
Jul 22 at 19:55
If there is an element of $[n]$ contained in exactly in one of the $A_i$'s, say $1in1,2,3$, then split $A_2,A_3,ldots,A_n$ into two groups---those that contain $2,3$ and those that are disjoint from $2,3$. Now, if there are $k$ of those that contain $2,3$, then there are at most $n-k-3$ of those that are disjoint from $2,3$. Thus, you can end up with at most $1+k+(n-k-3)=n-2$ sets.
– Batominovski
Jul 22 at 19:58
How you got $n-k-3$?
– greedoid
Jul 22 at 20:07
The sets of the first kind must be of the form $2,3,t_1,2,3,t_2,ldots,2,3,t_k$, and the sets of the second kind must be disjoint from $1,2,3,t_1,t_2,ldots,t_k$. Therefore, the sets of the second kind are subsets of $[n]setminus 1,2,3,t_1,t_2,ldots,t_k$, which has $n-k-3$ elements.
– Batominovski
Jul 22 at 20:12
I still don't understand. Why does this mean that we have at most n-k-3 subsets?
– greedoid
Jul 22 at 20:28
 |Â
show 1 more comment
up vote
1
down vote
Let $n$ be a positive integer. If $A_1,A_2,ldots,A_m$ are $3$-subsets of $[n]$ such that $left|A_icap A_jright|neq 1$ for $ineq j$, then the largest possible value of $m$ is
$$m_max=left{
beginarrayll
n&textif nequiv0pmod4,,\
n-1&textif nequiv1pmod4,,\
n-2&textelse,.
endarray
right.$$
Remark: Below is a sketch of my proof of the claim above. Be warned that a complete proof is quite long, whence I am providing a sketch with various gaps to be filled in. I hope that somebody will come up with a nicer proof.
Proof. The first two cases follow from my first answer. I shall now deal with the last case, where $m_max=n-2$.
Suppose contrary that there are $A_1,A_2,ldots,A_n-1$ satisfying the intersection condition. Then, proceed as before. The indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1inmathbbF_2^n$ are linearly independent. Thus, there exists $mathbfvinmathbbF_2^n$ such that $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1,mathbfb$ form a basis of $mathbbF_2^n$. We can assume that $langle mathbfa_i,mathbfbrangle=0$ for all $i=1,2,ldots,n-1$ (otherwise, replace $mathbfb$ by $mathbfb-sum_i=1^n-1,langle mathbfa_i,mathbfbrangle ,mathbfa_i$). Observe that $langle mathbfb,mathbfbrangle=1$.
Note that $$boldsymbol1=sum_i=1^n-1,mathbfa_i+mathbfb,.$$
Let $B$ be the subset of $[n]$ with the indicator vector $mathbfb$. Let $X$ denote the set of $i$ such that $A_i$ is disjoint from $B$, and $Y$ the set of $i$ such that $A_icap B$ has two elements. Observe that $X$ and $Y$ form a partition of $1,2,ldots,n-1$; moreover,
$$mathcalX:=bigcup_iin X,A_itext and mathcalY:=bigcup_iin Y,A_i$$
are disjoint subsets of $[n]$.
If $Xneq emptyset$, then we can use induction to finish the proof, noting that $A_isubseteq [n]setminus (BcupmathcalY)$ for all $iin X$. From now on, assume that $X=emptyset$.
Consider a simple graph $G$ on the vertex set $B$ where two vertices $i,jin B$ ($ineq j$) are connected by an edge iff $i$ and $j$ belongs in some $A_p$ simultaneously. If $C$ is a connected component of $G$ and $kin [n]setminus B$, then we say that $k$ is adjacent to $C$ if there exists $A_p$ such that $A_pcap B$ is an edge of $C$ and $kin A_p$, in which case, we also say that $A_p$ is incident to $C$. It is important to note that, if $C_1$ and $C_2$ are two distinct connected components of $G$, and $k_1,k_2in [n]setminus B$ are adjacent to $C_1$ and $C_2$, respectively, then $k_1neq k_2$.
Let $C$ be a connected component of $G$ with at least two vertices. We have three probable scenarios:
- $C$ is a type-1 connected component, namely, $C$ is an isolated edge (i.e., it has only two vertices and one edge);
- $C$ is a type-2 connected component, namely, $C$ is a triangle (i.e., $C$ consists of $3$ vertices and $3$ edges);
- $C$ is a type-3 connected component, namely, $C$ is a star graph (i.e., there exists a vertex $v$ of $C$ such that every edge of $C$ takes the form $v,w$, where $w$ is any vertex of $C$ distinct from $v$).
It can be readily seen that, if $C$ is a connected component of type 2 or type 3 of $G$, then $C$ is adjacent to exactly one element of $[n]setminus B$. If $G$ has a connected component $C$ of type 2, then the removal of vertices in $C$ along with the element $jin[n]setminus B$ which is adjacent to $C$ reduces the elements of $[n]$ by $4$, whilst ridding of only three sets $A_i$. Then, we finish the proof for this case by induction. Suppose from now on that $G$ has no connected components of type 2.
Now, assume that $G$ has a connected component $C$ of type 3, which has $s$ vertices. Let $jin[n]setminus B$ be adjacent to $C$. Then, the removal of vertices of $C$ along with $j$ from $[n]$ reduces the elements of $[n]$ by $s+1$, whilst ridding of only $s-1$ sets $A_i$. Therefore, the claim hold trivially.
Finally, assume that $G$ has only connected components of type 1 and possibly some isolated vertices. Then, it follows immediately that there are at most $n-2t$ sets $A_i$, where $t$ is the number of connected components of type 1. This shows that $t=0$. Thus, $G$ has only isolated vertices, but this is a contradiction as well (as $X=emptyset$ is assumed).
answered Jul 23 at 13:13
Batominovski
23.2k22777
This is very nice extension of the original problem. A will read it eventually.
– greedoid
Jul 23 at 14:01
Where did you get this problem from anyway?
– Batominovski
Jul 23 at 15:36
China Western Olympiad 2010 (I think)
– greedoid
Jul 23 at 15:36
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Suppose that there are $n$ such sets $A_1,A_2,ldots,A_n$, represented by indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_ninmathbbF_2^n$. Equip $mathbbF_2^n$ with the usual inner product $langle_,_rangle$.
We already know that the vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n$ are linearly independent. Therefore, they span $mathbbF_2^n$. Thus, the vector $boldsymbol1:=(1,1,ldots,1)$ can be written as
$$mathbfa_j_1+mathbfa_j_2+ldots+mathbfa_j_k$$
for some $j_1,j_2,ldots,j_kin1,2,ldots,n=:[n]$ with $j_1<j_2<ldots<j_k$. If $k<n$, then there exists $rin[n]$ such that $rneq j_mu$ for all $mu=1,2,ldots,k$. That is,
$$1=langle mathbfa_r,boldsymbol1rangle =sum_mu=1^k,langle mathbfa_j_mu,mathbfa_rrangle=0,,$$
which is a contradiction. Therefore, $k=n$, whence
$$boldsymbol1=sum_j=1^n,mathbfa_j,.tag*$$
Consequently, each element of $[n]$ belongs in an odd number of $A_1,A_2,ldots,A_n$, whence at least one of the sets $A_1,A_2,ldots,A_n$.
Furthermore, it is not difficult to show that every element of $[n]$ must belong in at least two of the $A_i$'s. (If there exists an element of $[n]$ belonging in exactly one $A_j$, then you can show that there are at most $n-2$ possible $A_i$'s.) Let $d_j$ be the number of sets $A_i$ such that $jin A_i$. Then
$$sum_j=1^n,d_j=3n,.tag#$$
Note that $d_jgeq 2$ for all $jin[n]$.
From (*), we conclude that $d_jgeq 3$ for every $jin[n]$. However, (#) implies that $d_j=3$ for all $jin[n]$; i.e., every element of $[n]$ must be in exactly three of the $A_i$'s. Write $mathbfe_1,mathbfe_2,ldots,mathbfe_n$ for the standard basis vectors of $mathbbF^n_2$. We see that
$$mathbfe_j=mathbfa_p+mathbfa_q+mathbfa_r$$
where $j$ is in $A_p$, $A_q$, and $A_r$. This shows that
$$A_p=j,x,y,,,,A_q=j,y,z,,text and A_r=j,z,x$$
for some $x,y,zin[n]$. Since $x$ already belongs in $A_p$ and $A_r$, it must be belong in another $A_s$. Clearly, $A_s$ must be equal to $x,y,z$. From here, we conclude that the four elements $j,x,y,z$ belong in exactly four of the $A_i$'s, which are $j,x,y,j,y,z,j,z,x,x,y,z$. The rest is easy.
answered Jul 22 at 19:21
Batominovski
23.2k22777
I read it all. All I have to check now why is $d_igeq 2$ for each $i$.
– greedoid
Jul 22 at 19:55
If there is an element of $[n]$ contained in exactly in one of the $A_i$'s, say $1in1,2,3$, then split $A_2,A_3,ldots,A_n$ into two groups---those that contain $2,3$ and those that are disjoint from $2,3$. Now, if there are $k$ of those that contain $2,3$, then there are at most $n-k-3$ of those that are disjoint from $2,3$. Thus, you can end up with at most $1+k+(n-k-3)=n-2$ sets.
– Batominovski
Jul 22 at 19:58
How you got $n-k-3$?
– greedoid
Jul 22 at 20:07
The sets of the first kind must be of the form $2,3,t_1,2,3,t_2,ldots,2,3,t_k$, and the sets of the second kind must be disjoint from $1,2,3,t_1,t_2,ldots,t_k$. Therefore, the sets of the second kind are subsets of $[n]setminus 1,2,3,t_1,t_2,ldots,t_k$, which has $n-k-3$ elements.
– Batominovski
Jul 22 at 20:12
I still don't understand. Why does this mean that we have at most n-k-3 subsets?
– greedoid
Jul 22 at 20:28
 |Â
show 1 more comment
up vote
2
down vote
accepted
Suppose that there are $n$ such sets $A_1,A_2,ldots,A_n$, represented by indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_ninmathbbF_2^n$. Equip $mathbbF_2^n$ with the usual inner product $langle_,_rangle$.
We already know that the vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n$ are linearly independent. Therefore, they span $mathbbF_2^n$. Thus, the vector $boldsymbol1:=(1,1,ldots,1)$ can be written as
$$mathbfa_j_1+mathbfa_j_2+ldots+mathbfa_j_k$$
for some $j_1,j_2,ldots,j_kin1,2,ldots,n=:[n]$ with $j_1<j_2<ldots<j_k$. If $k<n$, then there exists $rin[n]$ such that $rneq j_mu$ for all $mu=1,2,ldots,k$. That is,
$$1=langle mathbfa_r,boldsymbol1rangle =sum_mu=1^k,langle mathbfa_j_mu,mathbfa_rrangle=0,,$$
which is a contradiction. Therefore, $k=n$, whence
$$boldsymbol1=sum_j=1^n,mathbfa_j,.tag*$$
Consequently, each element of $[n]$ belongs in an odd number of $A_1,A_2,ldots,A_n$, whence at least one of the sets $A_1,A_2,ldots,A_n$.
Furthermore, it is not difficult to show that every element of $[n]$ must belong in at least two of the $A_i$'s. (If there exists an element of $[n]$ belonging in exactly one $A_j$, then you can show that there are at most $n-2$ possible $A_i$'s.) Let $d_j$ be the number of sets $A_i$ such that $jin A_i$. Then
$$sum_j=1^n,d_j=3n,.tag#$$
Note that $d_jgeq 2$ for all $jin[n]$.
From (*), we conclude that $d_jgeq 3$ for every $jin[n]$. However, (#) implies that $d_j=3$ for all $jin[n]$; i.e., every element of $[n]$ must be in exactly three of the $A_i$'s. Write $mathbfe_1,mathbfe_2,ldots,mathbfe_n$ for the standard basis vectors of $mathbbF^n_2$. We see that
$$mathbfe_j=mathbfa_p+mathbfa_q+mathbfa_r$$
where $j$ is in $A_p$, $A_q$, and $A_r$. This shows that
$$A_p=j,x,y,,,,A_q=j,y,z,,text and A_r=j,z,x$$
for some $x,y,zin[n]$. Since $x$ already belongs in $A_p$ and $A_r$, it must be belong in another $A_s$. Clearly, $A_s$ must be equal to $x,y,z$. From here, we conclude that the four elements $j,x,y,z$ belong in exactly four of the $A_i$'s, which are $j,x,y,j,y,z,j,z,x,x,y,z$. The rest is easy.
answered Jul 22 at 19:21
Batominovski
23.2k22777
I read it all. All I have to check now why is $d_igeq 2$ for each $i$.
– greedoid
Jul 22 at 19:55
If there is an element of $[n]$ contained in exactly in one of the $A_i$'s, say $1in1,2,3$, then split $A_2,A_3,ldots,A_n$ into two groups---those that contain $2,3$ and those that are disjoint from $2,3$. Now, if there are $k$ of those that contain $2,3$, then there are at most $n-k-3$ of those that are disjoint from $2,3$. Thus, you can end up with at most $1+k+(n-k-3)=n-2$ sets.
– Batominovski
Jul 22 at 19:58
How you got $n-k-3$?
– greedoid
Jul 22 at 20:07
The sets of the first kind must be of the form $2,3,t_1,2,3,t_2,ldots,2,3,t_k$, and the sets of the second kind must be disjoint from $1,2,3,t_1,t_2,ldots,t_k$. Therefore, the sets of the second kind are subsets of $[n]setminus 1,2,3,t_1,t_2,ldots,t_k$, which has $n-k-3$ elements.
– Batominovski
Jul 22 at 20:12
I still don't understand. Why does this mean that we have at most n-k-3 subsets?
– greedoid
Jul 22 at 20:28
 |Â
show 1 more comment
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Suppose that there are $n$ such sets $A_1,A_2,ldots,A_n$, represented by indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_ninmathbbF_2^n$. Equip $mathbbF_2^n$ with the usual inner product $langle_,_rangle$.
We already know that the vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n$ are linearly independent. Therefore, they span $mathbbF_2^n$. Thus, the vector $boldsymbol1:=(1,1,ldots,1)$ can be written as
$$mathbfa_j_1+mathbfa_j_2+ldots+mathbfa_j_k$$
for some $j_1,j_2,ldots,j_kin1,2,ldots,n=:[n]$ with $j_1<j_2<ldots<j_k$. If $k<n$, then there exists $rin[n]$ such that $rneq j_mu$ for all $mu=1,2,ldots,k$. That is,
$$1=langle mathbfa_r,boldsymbol1rangle =sum_mu=1^k,langle mathbfa_j_mu,mathbfa_rrangle=0,,$$
which is a contradiction. Therefore, $k=n$, whence
$$boldsymbol1=sum_j=1^n,mathbfa_j,.tag*$$
Consequently, each element of $[n]$ belongs in an odd number of $A_1,A_2,ldots,A_n$, whence at least one of the sets $A_1,A_2,ldots,A_n$.
Furthermore, it is not difficult to show that every element of $[n]$ must belong in at least two of the $A_i$'s. (If there exists an element of $[n]$ belonging in exactly one $A_j$, then you can show that there are at most $n-2$ possible $A_i$'s.) Let $d_j$ be the number of sets $A_i$ such that $jin A_i$. Then
$$sum_j=1^n,d_j=3n,.tag#$$
Note that $d_jgeq 2$ for all $jin[n]$.
From (*), we conclude that $d_jgeq 3$ for every $jin[n]$. However, (#) implies that $d_j=3$ for all $jin[n]$; i.e., every element of $[n]$ must be in exactly three of the $A_i$'s. Write $mathbfe_1,mathbfe_2,ldots,mathbfe_n$ for the standard basis vectors of $mathbbF^n_2$. We see that
$$mathbfe_j=mathbfa_p+mathbfa_q+mathbfa_r$$
where $j$ is in $A_p$, $A_q$, and $A_r$. This shows that
$$A_p=j,x,y,,,,A_q=j,y,z,,text and A_r=j,z,x$$
for some $x,y,zin[n]$. Since $x$ already belongs in $A_p$ and $A_r$, it must be belong in another $A_s$. Clearly, $A_s$ must be equal to $x,y,z$. From here, we conclude that the four elements $j,x,y,z$ belong in exactly four of the $A_i$'s, which are $j,x,y,j,y,z,j,z,x,x,y,z$. The rest is easy.
answered Jul 22 at 19:21
Batominovski
23.2k22777
Suppose that there are $n$ such sets $A_1,A_2,ldots,A_n$, represented by indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_ninmathbbF_2^n$. Equip $mathbbF_2^n$ with the usual inner product $langle_,_rangle$.
We already know that the vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n$ are linearly independent. Therefore, they span $mathbbF_2^n$. Thus, the vector $boldsymbol1:=(1,1,ldots,1)$ can be written as
$$mathbfa_j_1+mathbfa_j_2+ldots+mathbfa_j_k$$
for some $j_1,j_2,ldots,j_kin1,2,ldots,n=:[n]$ with $j_1<j_2<ldots<j_k$. If $k<n$, then there exists $rin[n]$ such that $rneq j_mu$ for all $mu=1,2,ldots,k$. That is,
$$1=langle mathbfa_r,boldsymbol1rangle =sum_mu=1^k,langle mathbfa_j_mu,mathbfa_rrangle=0,,$$
which is a contradiction. Therefore, $k=n$, whence
$$boldsymbol1=sum_j=1^n,mathbfa_j,.tag*$$
Consequently, each element of $[n]$ belongs in an odd number of $A_1,A_2,ldots,A_n$, whence at least one of the sets $A_1,A_2,ldots,A_n$.
Furthermore, it is not difficult to show that every element of $[n]$ must belong in at least two of the $A_i$'s. (If there exists an element of $[n]$ belonging in exactly one $A_j$, then you can show that there are at most $n-2$ possible $A_i$'s.) Let $d_j$ be the number of sets $A_i$ such that $jin A_i$. Then
$$sum_j=1^n,d_j=3n,.tag#$$
Note that $d_jgeq 2$ for all $jin[n]$.
From (*), we conclude that $d_jgeq 3$ for every $jin[n]$. However, (#) implies that $d_j=3$ for all $jin[n]$; i.e., every element of $[n]$ must be in exactly three of the $A_i$'s. Write $mathbfe_1,mathbfe_2,ldots,mathbfe_n$ for the standard basis vectors of $mathbbF^n_2$. We see that
$$mathbfe_j=mathbfa_p+mathbfa_q+mathbfa_r$$
where $j$ is in $A_p$, $A_q$, and $A_r$. This shows that
$$A_p=j,x,y,,,,A_q=j,y,z,,text and A_r=j,z,x$$
for some $x,y,zin[n]$. Since $x$ already belongs in $A_p$ and $A_r$, it must be belong in another $A_s$. Clearly, $A_s$ must be equal to $x,y,z$. From here, we conclude that the four elements $j,x,y,z$ belong in exactly four of the $A_i$'s, which are $j,x,y,j,y,z,j,z,x,x,y,z$. The rest is easy.
answered Jul 22 at 19:21
Batominovski
23.2k22777
edited Jul 23 at 11:40
answered Jul 22 at 19:21
Batominovski
23.2k22777
answered Jul 22 at 19:21
Batominovski
23.2k22777
answered Jul 22 at 19:21
Batominovski
23.2k22777
23.2k22777
I read it all. All I have to check now why is $d_igeq 2$ for each $i$.
– greedoid
Jul 22 at 19:55
If there is an element of $[n]$ contained in exactly in one of the $A_i$'s, say $1in1,2,3$, then split $A_2,A_3,ldots,A_n$ into two groups---those that contain $2,3$ and those that are disjoint from $2,3$. Now, if there are $k$ of those that contain $2,3$, then there are at most $n-k-3$ of those that are disjoint from $2,3$. Thus, you can end up with at most $1+k+(n-k-3)=n-2$ sets.
– Batominovski
Jul 22 at 19:58
How you got $n-k-3$?
– greedoid
Jul 22 at 20:07
The sets of the first kind must be of the form $2,3,t_1,2,3,t_2,ldots,2,3,t_k$, and the sets of the second kind must be disjoint from $1,2,3,t_1,t_2,ldots,t_k$. Therefore, the sets of the second kind are subsets of $[n]setminus 1,2,3,t_1,t_2,ldots,t_k$, which has $n-k-3$ elements.
– Batominovski
Jul 22 at 20:12
I still don't understand. Why does this mean that we have at most n-k-3 subsets?
– greedoid
Jul 22 at 20:28
 |Â
show 1 more comment
I read it all. All I have to check now why is $d_igeq 2$ for each $i$.
– greedoid
Jul 22 at 19:55
If there is an element of $[n]$ contained in exactly in one of the $A_i$'s, say $1in1,2,3$, then split $A_2,A_3,ldots,A_n$ into two groups---those that contain $2,3$ and those that are disjoint from $2,3$. Now, if there are $k$ of those that contain $2,3$, then there are at most $n-k-3$ of those that are disjoint from $2,3$. Thus, you can end up with at most $1+k+(n-k-3)=n-2$ sets.
– Batominovski
Jul 22 at 19:58
How you got $n-k-3$?
– greedoid
Jul 22 at 20:07
The sets of the first kind must be of the form $2,3,t_1,2,3,t_2,ldots,2,3,t_k$, and the sets of the second kind must be disjoint from $1,2,3,t_1,t_2,ldots,t_k$. Therefore, the sets of the second kind are subsets of $[n]setminus 1,2,3,t_1,t_2,ldots,t_k$, which has $n-k-3$ elements.
– Batominovski
Jul 22 at 20:12
I still don't understand. Why does this mean that we have at most n-k-3 subsets?
– greedoid
Jul 22 at 20:28
I read it all. All I have to check now why is $d_igeq 2$ for each $i$.
– greedoid
Jul 22 at 19:55
I read it all. All I have to check now why is $d_igeq 2$ for each $i$.
– greedoid
Jul 22 at 19:55
If there is an element of $[n]$ contained in exactly in one of the $A_i$'s, say $1in1,2,3$, then split $A_2,A_3,ldots,A_n$ into two groups---those that contain $2,3$ and those that are disjoint from $2,3$. Now, if there are $k$ of those that contain $2,3$, then there are at most $n-k-3$ of those that are disjoint from $2,3$. Thus, you can end up with at most $1+k+(n-k-3)=n-2$ sets.
– Batominovski
Jul 22 at 19:58
If there is an element of $[n]$ contained in exactly in one of the $A_i$'s, say $1in1,2,3$, then split $A_2,A_3,ldots,A_n$ into two groups---those that contain $2,3$ and those that are disjoint from $2,3$. Now, if there are $k$ of those that contain $2,3$, then there are at most $n-k-3$ of those that are disjoint from $2,3$. Thus, you can end up with at most $1+k+(n-k-3)=n-2$ sets.
– Batominovski
Jul 22 at 19:58
How you got $n-k-3$?
– greedoid
Jul 22 at 20:07
How you got $n-k-3$?
– greedoid
Jul 22 at 20:07
The sets of the first kind must be of the form $2,3,t_1,2,3,t_2,ldots,2,3,t_k$, and the sets of the second kind must be disjoint from $1,2,3,t_1,t_2,ldots,t_k$. Therefore, the sets of the second kind are subsets of $[n]setminus 1,2,3,t_1,t_2,ldots,t_k$, which has $n-k-3$ elements.
– Batominovski
Jul 22 at 20:12
The sets of the first kind must be of the form $2,3,t_1,2,3,t_2,ldots,2,3,t_k$, and the sets of the second kind must be disjoint from $1,2,3,t_1,t_2,ldots,t_k$. Therefore, the sets of the second kind are subsets of $[n]setminus 1,2,3,t_1,t_2,ldots,t_k$, which has $n-k-3$ elements.
– Batominovski
Jul 22 at 20:12
I still don't understand. Why does this mean that we have at most n-k-3 subsets?
– greedoid
Jul 22 at 20:28
I still don't understand. Why does this mean that we have at most n-k-3 subsets?
– greedoid
Jul 22 at 20:28
 |Â
show 1 more comment
up vote
1
down vote
Let $n$ be a positive integer. If $A_1,A_2,ldots,A_m$ are $3$-subsets of $[n]$ such that $left|A_icap A_jright|neq 1$ for $ineq j$, then the largest possible value of $m$ is
$$m_max=left{
beginarrayll
n&textif nequiv0pmod4,,\
n-1&textif nequiv1pmod4,,\
n-2&textelse,.
endarray
right.$$
Remark: Below is a sketch of my proof of the claim above. Be warned that a complete proof is quite long, whence I am providing a sketch with various gaps to be filled in. I hope that somebody will come up with a nicer proof.
Proof. The first two cases follow from my first answer. I shall now deal with the last case, where $m_max=n-2$.
Suppose contrary that there are $A_1,A_2,ldots,A_n-1$ satisfying the intersection condition. Then, proceed as before. The indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1inmathbbF_2^n$ are linearly independent. Thus, there exists $mathbfvinmathbbF_2^n$ such that $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1,mathbfb$ form a basis of $mathbbF_2^n$. We can assume that $langle mathbfa_i,mathbfbrangle=0$ for all $i=1,2,ldots,n-1$ (otherwise, replace $mathbfb$ by $mathbfb-sum_i=1^n-1,langle mathbfa_i,mathbfbrangle ,mathbfa_i$). Observe that $langle mathbfb,mathbfbrangle=1$.
Note that $$boldsymbol1=sum_i=1^n-1,mathbfa_i+mathbfb,.$$
Let $B$ be the subset of $[n]$ with the indicator vector $mathbfb$. Let $X$ denote the set of $i$ such that $A_i$ is disjoint from $B$, and $Y$ the set of $i$ such that $A_icap B$ has two elements. Observe that $X$ and $Y$ form a partition of $1,2,ldots,n-1$; moreover,
$$mathcalX:=bigcup_iin X,A_itext and mathcalY:=bigcup_iin Y,A_i$$
are disjoint subsets of $[n]$.
If $Xneq emptyset$, then we can use induction to finish the proof, noting that $A_isubseteq [n]setminus (BcupmathcalY)$ for all $iin X$. From now on, assume that $X=emptyset$.
Consider a simple graph $G$ on the vertex set $B$ where two vertices $i,jin B$ ($ineq j$) are connected by an edge iff $i$ and $j$ belongs in some $A_p$ simultaneously. If $C$ is a connected component of $G$ and $kin [n]setminus B$, then we say that $k$ is adjacent to $C$ if there exists $A_p$ such that $A_pcap B$ is an edge of $C$ and $kin A_p$, in which case, we also say that $A_p$ is incident to $C$. It is important to note that, if $C_1$ and $C_2$ are two distinct connected components of $G$, and $k_1,k_2in [n]setminus B$ are adjacent to $C_1$ and $C_2$, respectively, then $k_1neq k_2$.
Let $C$ be a connected component of $G$ with at least two vertices. We have three probable scenarios:
- $C$ is a type-1 connected component, namely, $C$ is an isolated edge (i.e., it has only two vertices and one edge);
- $C$ is a type-2 connected component, namely, $C$ is a triangle (i.e., $C$ consists of $3$ vertices and $3$ edges);
- $C$ is a type-3 connected component, namely, $C$ is a star graph (i.e., there exists a vertex $v$ of $C$ such that every edge of $C$ takes the form $v,w$, where $w$ is any vertex of $C$ distinct from $v$).
It can be readily seen that, if $C$ is a connected component of type 2 or type 3 of $G$, then $C$ is adjacent to exactly one element of $[n]setminus B$. If $G$ has a connected component $C$ of type 2, then the removal of vertices in $C$ along with the element $jin[n]setminus B$ which is adjacent to $C$ reduces the elements of $[n]$ by $4$, whilst ridding of only three sets $A_i$. Then, we finish the proof for this case by induction. Suppose from now on that $G$ has no connected components of type 2.
Now, assume that $G$ has a connected component $C$ of type 3, which has $s$ vertices. Let $jin[n]setminus B$ be adjacent to $C$. Then, the removal of vertices of $C$ along with $j$ from $[n]$ reduces the elements of $[n]$ by $s+1$, whilst ridding of only $s-1$ sets $A_i$. Therefore, the claim hold trivially.
Finally, assume that $G$ has only connected components of type 1 and possibly some isolated vertices. Then, it follows immediately that there are at most $n-2t$ sets $A_i$, where $t$ is the number of connected components of type 1. This shows that $t=0$. Thus, $G$ has only isolated vertices, but this is a contradiction as well (as $X=emptyset$ is assumed).
answered Jul 23 at 13:13
Batominovski
23.2k22777
This is very nice extension of the original problem. A will read it eventually.
– greedoid
Jul 23 at 14:01
Where did you get this problem from anyway?
– Batominovski
Jul 23 at 15:36
China Western Olympiad 2010 (I think)
– greedoid
Jul 23 at 15:36
add a comment |Â
up vote
1
down vote
Let $n$ be a positive integer. If $A_1,A_2,ldots,A_m$ are $3$-subsets of $[n]$ such that $left|A_icap A_jright|neq 1$ for $ineq j$, then the largest possible value of $m$ is
$$m_max=left{
beginarrayll
n&textif nequiv0pmod4,,\
n-1&textif nequiv1pmod4,,\
n-2&textelse,.
endarray
right.$$
Remark: Below is a sketch of my proof of the claim above. Be warned that a complete proof is quite long, whence I am providing a sketch with various gaps to be filled in. I hope that somebody will come up with a nicer proof.
Proof. The first two cases follow from my first answer. I shall now deal with the last case, where $m_max=n-2$.
Suppose contrary that there are $A_1,A_2,ldots,A_n-1$ satisfying the intersection condition. Then, proceed as before. The indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1inmathbbF_2^n$ are linearly independent. Thus, there exists $mathbfvinmathbbF_2^n$ such that $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1,mathbfb$ form a basis of $mathbbF_2^n$. We can assume that $langle mathbfa_i,mathbfbrangle=0$ for all $i=1,2,ldots,n-1$ (otherwise, replace $mathbfb$ by $mathbfb-sum_i=1^n-1,langle mathbfa_i,mathbfbrangle ,mathbfa_i$). Observe that $langle mathbfb,mathbfbrangle=1$.
Note that $$boldsymbol1=sum_i=1^n-1,mathbfa_i+mathbfb,.$$
Let $B$ be the subset of $[n]$ with the indicator vector $mathbfb$. Let $X$ denote the set of $i$ such that $A_i$ is disjoint from $B$, and $Y$ the set of $i$ such that $A_icap B$ has two elements. Observe that $X$ and $Y$ form a partition of $1,2,ldots,n-1$; moreover,
$$mathcalX:=bigcup_iin X,A_itext and mathcalY:=bigcup_iin Y,A_i$$
are disjoint subsets of $[n]$.
If $Xneq emptyset$, then we can use induction to finish the proof, noting that $A_isubseteq [n]setminus (BcupmathcalY)$ for all $iin X$. From now on, assume that $X=emptyset$.
Consider a simple graph $G$ on the vertex set $B$ where two vertices $i,jin B$ ($ineq j$) are connected by an edge iff $i$ and $j$ belongs in some $A_p$ simultaneously. If $C$ is a connected component of $G$ and $kin [n]setminus B$, then we say that $k$ is adjacent to $C$ if there exists $A_p$ such that $A_pcap B$ is an edge of $C$ and $kin A_p$, in which case, we also say that $A_p$ is incident to $C$. It is important to note that, if $C_1$ and $C_2$ are two distinct connected components of $G$, and $k_1,k_2in [n]setminus B$ are adjacent to $C_1$ and $C_2$, respectively, then $k_1neq k_2$.
Let $C$ be a connected component of $G$ with at least two vertices. We have three probable scenarios:
- $C$ is a type-1 connected component, namely, $C$ is an isolated edge (i.e., it has only two vertices and one edge);
- $C$ is a type-2 connected component, namely, $C$ is a triangle (i.e., $C$ consists of $3$ vertices and $3$ edges);
- $C$ is a type-3 connected component, namely, $C$ is a star graph (i.e., there exists a vertex $v$ of $C$ such that every edge of $C$ takes the form $v,w$, where $w$ is any vertex of $C$ distinct from $v$).
It can be readily seen that, if $C$ is a connected component of type 2 or type 3 of $G$, then $C$ is adjacent to exactly one element of $[n]setminus B$. If $G$ has a connected component $C$ of type 2, then the removal of vertices in $C$ along with the element $jin[n]setminus B$ which is adjacent to $C$ reduces the elements of $[n]$ by $4$, whilst ridding of only three sets $A_i$. Then, we finish the proof for this case by induction. Suppose from now on that $G$ has no connected components of type 2.
Now, assume that $G$ has a connected component $C$ of type 3, which has $s$ vertices. Let $jin[n]setminus B$ be adjacent to $C$. Then, the removal of vertices of $C$ along with $j$ from $[n]$ reduces the elements of $[n]$ by $s+1$, whilst ridding of only $s-1$ sets $A_i$. Therefore, the claim hold trivially.
Finally, assume that $G$ has only connected components of type 1 and possibly some isolated vertices. Then, it follows immediately that there are at most $n-2t$ sets $A_i$, where $t$ is the number of connected components of type 1. This shows that $t=0$. Thus, $G$ has only isolated vertices, but this is a contradiction as well (as $X=emptyset$ is assumed).
answered Jul 23 at 13:13
Batominovski
23.2k22777
This is very nice extension of the original problem. A will read it eventually.
– greedoid
Jul 23 at 14:01
Where did you get this problem from anyway?
– Batominovski
Jul 23 at 15:36
China Western Olympiad 2010 (I think)
– greedoid
Jul 23 at 15:36
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let $n$ be a positive integer. If $A_1,A_2,ldots,A_m$ are $3$-subsets of $[n]$ such that $left|A_icap A_jright|neq 1$ for $ineq j$, then the largest possible value of $m$ is
$$m_max=left{
beginarrayll
n&textif nequiv0pmod4,,\
n-1&textif nequiv1pmod4,,\
n-2&textelse,.
endarray
right.$$
Remark: Below is a sketch of my proof of the claim above. Be warned that a complete proof is quite long, whence I am providing a sketch with various gaps to be filled in. I hope that somebody will come up with a nicer proof.
Proof. The first two cases follow from my first answer. I shall now deal with the last case, where $m_max=n-2$.
Suppose contrary that there are $A_1,A_2,ldots,A_n-1$ satisfying the intersection condition. Then, proceed as before. The indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1inmathbbF_2^n$ are linearly independent. Thus, there exists $mathbfvinmathbbF_2^n$ such that $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1,mathbfb$ form a basis of $mathbbF_2^n$. We can assume that $langle mathbfa_i,mathbfbrangle=0$ for all $i=1,2,ldots,n-1$ (otherwise, replace $mathbfb$ by $mathbfb-sum_i=1^n-1,langle mathbfa_i,mathbfbrangle ,mathbfa_i$). Observe that $langle mathbfb,mathbfbrangle=1$.
Note that $$boldsymbol1=sum_i=1^n-1,mathbfa_i+mathbfb,.$$
Let $B$ be the subset of $[n]$ with the indicator vector $mathbfb$. Let $X$ denote the set of $i$ such that $A_i$ is disjoint from $B$, and $Y$ the set of $i$ such that $A_icap B$ has two elements. Observe that $X$ and $Y$ form a partition of $1,2,ldots,n-1$; moreover,
$$mathcalX:=bigcup_iin X,A_itext and mathcalY:=bigcup_iin Y,A_i$$
are disjoint subsets of $[n]$.
If $Xneq emptyset$, then we can use induction to finish the proof, noting that $A_isubseteq [n]setminus (BcupmathcalY)$ for all $iin X$. From now on, assume that $X=emptyset$.
Consider a simple graph $G$ on the vertex set $B$ where two vertices $i,jin B$ ($ineq j$) are connected by an edge iff $i$ and $j$ belongs in some $A_p$ simultaneously. If $C$ is a connected component of $G$ and $kin [n]setminus B$, then we say that $k$ is adjacent to $C$ if there exists $A_p$ such that $A_pcap B$ is an edge of $C$ and $kin A_p$, in which case, we also say that $A_p$ is incident to $C$. It is important to note that, if $C_1$ and $C_2$ are two distinct connected components of $G$, and $k_1,k_2in [n]setminus B$ are adjacent to $C_1$ and $C_2$, respectively, then $k_1neq k_2$.
Let $C$ be a connected component of $G$ with at least two vertices. We have three probable scenarios:
- $C$ is a type-1 connected component, namely, $C$ is an isolated edge (i.e., it has only two vertices and one edge);
- $C$ is a type-2 connected component, namely, $C$ is a triangle (i.e., $C$ consists of $3$ vertices and $3$ edges);
- $C$ is a type-3 connected component, namely, $C$ is a star graph (i.e., there exists a vertex $v$ of $C$ such that every edge of $C$ takes the form $v,w$, where $w$ is any vertex of $C$ distinct from $v$).
It can be readily seen that, if $C$ is a connected component of type 2 or type 3 of $G$, then $C$ is adjacent to exactly one element of $[n]setminus B$. If $G$ has a connected component $C$ of type 2, then the removal of vertices in $C$ along with the element $jin[n]setminus B$ which is adjacent to $C$ reduces the elements of $[n]$ by $4$, whilst ridding of only three sets $A_i$. Then, we finish the proof for this case by induction. Suppose from now on that $G$ has no connected components of type 2.
Now, assume that $G$ has a connected component $C$ of type 3, which has $s$ vertices. Let $jin[n]setminus B$ be adjacent to $C$. Then, the removal of vertices of $C$ along with $j$ from $[n]$ reduces the elements of $[n]$ by $s+1$, whilst ridding of only $s-1$ sets $A_i$. Therefore, the claim hold trivially.
Finally, assume that $G$ has only connected components of type 1 and possibly some isolated vertices. Then, it follows immediately that there are at most $n-2t$ sets $A_i$, where $t$ is the number of connected components of type 1. This shows that $t=0$. Thus, $G$ has only isolated vertices, but this is a contradiction as well (as $X=emptyset$ is assumed).
answered Jul 23 at 13:13
Batominovski
23.2k22777
Let $n$ be a positive integer. If $A_1,A_2,ldots,A_m$ are $3$-subsets of $[n]$ such that $left|A_icap A_jright|neq 1$ for $ineq j$, then the largest possible value of $m$ is
$$m_max=left{
beginarrayll
n&textif nequiv0pmod4,,\
n-1&textif nequiv1pmod4,,\
n-2&textelse,.
endarray
right.$$
Remark: Below is a sketch of my proof of the claim above. Be warned that a complete proof is quite long, whence I am providing a sketch with various gaps to be filled in. I hope that somebody will come up with a nicer proof.
Proof. The first two cases follow from my first answer. I shall now deal with the last case, where $m_max=n-2$.
Suppose contrary that there are $A_1,A_2,ldots,A_n-1$ satisfying the intersection condition. Then, proceed as before. The indicator vectors $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1inmathbbF_2^n$ are linearly independent. Thus, there exists $mathbfvinmathbbF_2^n$ such that $mathbfa_1,mathbfa_2,ldots,mathbfa_n-1,mathbfb$ form a basis of $mathbbF_2^n$. We can assume that $langle mathbfa_i,mathbfbrangle=0$ for all $i=1,2,ldots,n-1$ (otherwise, replace $mathbfb$ by $mathbfb-sum_i=1^n-1,langle mathbfa_i,mathbfbrangle ,mathbfa_i$). Observe that $langle mathbfb,mathbfbrangle=1$.
Note that $$boldsymbol1=sum_i=1^n-1,mathbfa_i+mathbfb,.$$
Let $B$ be the subset of $[n]$ with the indicator vector $mathbfb$. Let $X$ denote the set of $i$ such that $A_i$ is disjoint from $B$, and $Y$ the set of $i$ such that $A_icap B$ has two elements. Observe that $X$ and $Y$ form a partition of $1,2,ldots,n-1$; moreover,
$$mathcalX:=bigcup_iin X,A_itext and mathcalY:=bigcup_iin Y,A_i$$
are disjoint subsets of $[n]$.
If $Xneq emptyset$, then we can use induction to finish the proof, noting that $A_isubseteq [n]setminus (BcupmathcalY)$ for all $iin X$. From now on, assume that $X=emptyset$.
Consider a simple graph $G$ on the vertex set $B$ where two vertices $i,jin B$ ($ineq j$) are connected by an edge iff $i$ and $j$ belongs in some $A_p$ simultaneously. If $C$ is a connected component of $G$ and $kin [n]setminus B$, then we say that $k$ is adjacent to $C$ if there exists $A_p$ such that $A_pcap B$ is an edge of $C$ and $kin A_p$, in which case, we also say that $A_p$ is incident to $C$. It is important to note that, if $C_1$ and $C_2$ are two distinct connected components of $G$, and $k_1,k_2in [n]setminus B$ are adjacent to $C_1$ and $C_2$, respectively, then $k_1neq k_2$.
Let $C$ be a connected component of $G$ with at least two vertices. We have three probable scenarios:
- $C$ is a type-1 connected component, namely, $C$ is an isolated edge (i.e., it has only two vertices and one edge);
- $C$ is a type-2 connected component, namely, $C$ is a triangle (i.e., $C$ consists of $3$ vertices and $3$ edges);
- $C$ is a type-3 connected component, namely, $C$ is a star graph (i.e., there exists a vertex $v$ of $C$ such that every edge of $C$ takes the form $v,w$, where $w$ is any vertex of $C$ distinct from $v$).
It can be readily seen that, if $C$ is a connected component of type 2 or type 3 of $G$, then $C$ is adjacent to exactly one element of $[n]setminus B$. If $G$ has a connected component $C$ of type 2, then the removal of vertices in $C$ along with the element $jin[n]setminus B$ which is adjacent to $C$ reduces the elements of $[n]$ by $4$, whilst ridding of only three sets $A_i$. Then, we finish the proof for this case by induction. Suppose from now on that $G$ has no connected components of type 2.
Now, assume that $G$ has a connected component $C$ of type 3, which has $s$ vertices. Let $jin[n]setminus B$ be adjacent to $C$. Then, the removal of vertices of $C$ along with $j$ from $[n]$ reduces the elements of $[n]$ by $s+1$, whilst ridding of only $s-1$ sets $A_i$. Therefore, the claim hold trivially.
Finally, assume that $G$ has only connected components of type 1 and possibly some isolated vertices. Then, it follows immediately that there are at most $n-2t$ sets $A_i$, where $t$ is the number of connected components of type 1. This shows that $t=0$. Thus, $G$ has only isolated vertices, but this is a contradiction as well (as $X=emptyset$ is assumed).
answered Jul 23 at 13:13
Batominovski
23.2k22777
edited Jul 23 at 14:49
answered Jul 23 at 13:13
Batominovski
23.2k22777
answered Jul 23 at 13:13
Batominovski
23.2k22777
answered Jul 23 at 13:13
Batominovski
23.2k22777
23.2k22777
This is very nice extension of the original problem. A will read it eventually.
– greedoid
Jul 23 at 14:01
Where did you get this problem from anyway?
– Batominovski
Jul 23 at 15:36
China Western Olympiad 2010 (I think)
– greedoid
Jul 23 at 15:36
add a comment |Â
This is very nice extension of the original problem. A will read it eventually.
– greedoid
Jul 23 at 14:01
Where did you get this problem from anyway?
– Batominovski
Jul 23 at 15:36
China Western Olympiad 2010 (I think)
– greedoid
Jul 23 at 15:36
This is very nice extension of the original problem. A will read it eventually.
– greedoid
Jul 23 at 14:01
This is very nice extension of the original problem. A will read it eventually.
– greedoid
Jul 23 at 14:01
Where did you get this problem from anyway?
– Batominovski
Jul 23 at 15:36
Where did you get this problem from anyway?
– Batominovski
Jul 23 at 15:36
China Western Olympiad 2010 (I think)
– greedoid
Jul 23 at 15:36
China Western Olympiad 2010 (I think)
– greedoid
Jul 23 at 15:36
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859673%2fthere-are-n-different-3-element-subsets-a-1-a-2-a-n-of-the-set-1-2%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password