Some Combinatorics
by djmathman, Jan 5, 2018, 1:43 AM
hey look I can actually do some of the questions from my Combo 3 notes now
Quote:
Write 
, the set of natural numbers, as
, the set of natural numbers, as
- a union of
pairwisely disjoint infinite sets. - an infinite union of pairwisely disjoint infinite sets.
pairwisely disjoint infinite sets.
,![\[S_k = \{n\in\mathbb N : n\equiv k\pmod{2011}\}.\]](http://latex.artofproblemsolving.com/2/0/7/207203320e83408e296b1f84764dd36253ffac28.png)
Then 
partition 
,![\[S_k = \{k + n^2:n\in\mathbb N\},\]](http://latex.artofproblemsolving.com/8/0/e/80e9f20aa7b3e4043085489e2aeec9be30cc8a50.png)
and define 
inductively via 
and ![\[T_{n+1} = S_{n+1}\setminus\bigcup_{i=0}^nT_i.\]](http://latex.artofproblemsolving.com/a/6/7/a67147e712fbf5676e4309803e7a8e720fa5756b.png)
For example, 
is the set of perfect squares, 
is the set of integers one more than a perfect square that are not perfect squares, and so on. Then each 
is infinite and 
partitions Quote:
Let 
be a nonempty set, and let 
be an increasing function on the set of subsets of , meaning that 
if 
. Prove that there exists 
, a subset of , such that 
.
be a nonempty set, and let 
be an increasing function on the set of subsets of , meaning that 
if 
. Prove that there exists 
, a subset of , such that 
.
inductively. Set 
.
,
,
.
.
,
.
for all 
.![\[T = \bigcup_{i\in\mathbb N}T_i.\]](http://latex.artofproblemsolving.com/d/0/d/d0d0b3e9b6de351c61d86c6f6c37f314791d8e02.png)
I claim that 
)
,
such that 
.
for some 
,![\[y = f(x)\in f(T_i) = T_{i+1}\subseteq T.\]](http://latex.artofproblemsolving.com/8/2/6/826040a161d96f4df9a1e0d7e9ac01daea875e74.png)
Since 
was arbitrary, we deduce that 
.
)
,
implies ![\[f(T)\supseteq f(T_n) = T_{n+1}.\]](http://latex.artofproblemsolving.com/b/5/d/b5d09636d0d6adcf5b6abad20c9a30a0e4c580f1.png)
Since this holds for all 
.Quote:
Let 
be a family of subsets of the set 
such that every element in has cardinality 
and moreover for any two distinct elements 
we have 
. Prove that ![\[|\mathcal F|\leq\frac{n(n-1)}6.\]](//latex.artofproblemsolving.com/9/7/6/976992e37d349f83d8a6c01c54ac6d0b54b83fc5.png)
be a family of subsets of the set 
such that every element in has cardinality 
and moreover for any two distinct elements 
we have 
. Prove that ![\[|\mathcal F|\leq\frac{n(n-1)}6.\]](http://latex.artofproblemsolving.com/9/7/6/976992e37d349f83d8a6c01c54ac6d0b54b83fc5.png)
![\[3|\mathcal F|\leq\frac{n(n-1)}2.\]](http://latex.artofproblemsolving.com/5/2/b/52bc49829cde4202e929257aaf5e5e02baa0f1e8.png)
Write ![\begin{align*}3|\mathcal F| &= \sum_{A\in \mathcal F}|A| = \sum_{A\in\mathcal F}\sum_{x\in A}1\\&=\sum_{x\in[n]}\sum_{A\in\mathcal F:x\in A}1 = \sum_{x\in[n]}|\{A\in\mathcal F: x\in A\}|.\end{align*}](http://latex.artofproblemsolving.com/2/f/7/2f7bb6b9da035f9b49b9e8de9575d8821d6fbba4.png)
Now I claim for any ![$x\in[n]$](http://latex.artofproblemsolving.com/9/d/a/9da7dbaa599ea64018322a2a731de340b6cad219.png)
,
.
are the sets in question. Note that for any 
and 
,
and 
,
and 
must be disjoint, meaning that 
.
which simplifies to 
as desired. As a result, ![\[3|\mathcal F| = \sum_{x\in[n]}|\{A\in\mathcal F: x\in A\}|\leq\sum_{x\in[n]}\frac{n-1}2 = \frac{n(n-1)}2,\]](http://latex.artofproblemsolving.com/6/e/8/6e81986078651014f94b9705f7ce91a76103680e.png)
and so we are done.This post has been edited 2 times. Last edited by djmathman, Jan 5, 2018, 1:47 AM
April 2025
November 2024