Infinite number of sets with an intersection property

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Infinite number of sets with an intersection property

G H J

Reveal topic tags

analytic geometry

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Romania TST 2013 Test 2 Problem 4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

88 posts

#1 h Apr 26, 2013, 3:52 PM • 3 Y

Y by nicegeo, doxuanlong15052000, Adventure10

Let $k$ be a positive integer larger than $1$ . Build an infinite set $\mathcal{A}$ of subsets of $\mathbb{N}$ having the following properties:

(a) any $k$ distinct sets of $\mathcal{A}$ have exactly one common element;
(b) any $k+1$ distinct sets of $\mathcal{A}$ have void intersection.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tenniskidperson3

2376 posts

tenniskidperson3

#2 h Apr 27, 2013, 3:57 AM • 2 Y

Y by dgrozev, Adventure10

Enumerate the $k$ -tuples; $(a_1, a_2, \ldots a_k)\rightarrow \binom{a_1}{1}+\binom{a_2-1}{2}+\binom{a_3-1}{3}+\ldots+\binom{a_k-1}{k}$ gives one method, where $a_1<a_2<a_3<\ldots<a_k$ . Put $n$ into each of the $k$ sets with indices $a_i$ correlating to $n$ . Then each $k$ -tuple contains a unique element, and no number is contained in $k+1$ sets.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2472 posts

#3 h Apr 27, 2013, 7:18 AM • 4 Y

Y by nghiepdu-socap, Adventure10, Mango247, and 1 other user

tenniskidperson3 wrote:

Enumerate the $k$ -tuples; $(a_1, a_2, \ldots a_k)\rightarrow \binom{a_1}{1}+\binom{a_2-1}{2}+\binom{a_3-1}{3}+\ldots+\binom{a_k-1}{k}$ gives one method, where $a_1<a_2<a_3<\ldots<a_k$ . Put $n$ into each of the $k$ sets with indices $a_i$ correlating to $n$ . Then each $k$ -tuple contains a unique element, and no number is contained in $k+1$ sets.

I really don't understand the above construction but it is not possible that a set in the family $\mathcal{A}$ consists of finite number of elements.

A construction of family $\mathcal{A}$ :
When $k=2$ consider infinite many lines in a plane in general positions. When $k=3$ - infinite many planes in space in general positions will do the job. Of course a line(plane) consists of points with real coordinates, not in $\mathbb{N}$ , but it just gives as a motivation.

Let $\{a_i\}_{i=1}^{\infty}$ be be a sequence of real numbers which are pairwise different and $a_i \neq 0$ .
Let denote:

$P_j = \left\{ (x_1,x_2,\ldots,x_{k}) \mid x_i\in \mathbb{R}, \sum_{i=1}^{k} a_j^i x_i -1 =0 \right\}$
$j=1,2,\ldots$ .

Now lets see that every $k$ different hyperplanes $P_{j_{\ell}},\, \ell=1,2,\ldots,k$ have exactly one common point $(x_1,x_2,\ldots,x_{k})$ . This common point will satisfy the system

$\sum_{i=1}^{k} a_{j_{\ell}}^i x_i = 1 \,,\, \ell=1,2,\ldots, k$

But the determinant of the system is exactly the Vandermonde determinant $V=\prod_{t=1}^{k} a_{j_{t}}\prod_{1 \leq s < t \leq k} ( a_{j_{t}}-a_{j_{s}} ) \neq 0$ . So the above system has an unique solution.
To see that every $k+1$ different planes have void intersection, assume on the contrary the hyperplanes $P_{j_{\ell}},\, \ell=1,2,\ldots,k+1$ have a common point $(x_1,x_2,\ldots,x_{k})$
Then the polynomial: $P(x)= x_1 x^1+x_2x^2+\ldots+x_k x^k-1$ will have $k+1$ different roots $a_{j_{\ell}},\, \ell=1,2,\ldots, k+1$ , which means $P(x)$ is identically zero which is impossible.

Now, it could have finished the proof but our sets must consist of natural numbers not of real $k$ -tuples.
But we can enumerate all possible intersections of $k$ different hyperplanes $P_j$ and let they be the points $\{p_{\ell}\}_{\ell=1}^{\infty}$ . Now consider:

$P'_j = \left\{\ell \mid \ell\in \mathbb{N},\, p_{\ell} \in P_j \right\}$ .

These modified discrete sets will also satisfy the requirements (a) and (b).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

212 posts

Lawasu

#4 h May 3, 2013, 9:47 AM • 7 Y

Y by siddigss, Wolstenholme, doxuanlong15052000, B.J.W.T, nguyennam_2020, Adventure10, Mango247

My construction:

For a number $n=p_1^{a_1}\cdot p_2^{a_2}\cdot ...\cdot p_m^{a_m}$ (its decomposition in prime factors) take $f(n)=a_1+a_2+...+a_m$ .
Now, for each prime $p$ take $A_p=\{px|\ x\in \Bbb{N},\ f(x)=k-1\}$ . Now it's trivial to check the given conditions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6882 posts

#5 h Dec 12, 2014, 1:22 PM • 3 Y

Y by dgrozev, Adventure10, Mango247

dgrozev wrote:

I really don't understand the above construction but it is not possible that a set in the family $\mathcal{A}$ consists of finite number of elements.

Is this an issue? The problem statement didn't seem to require finite sets...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2472 posts

#6 h Dec 13, 2014, 9:07 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

What I meant was that it's impossible some set in $\mathcal{A}$ to be finite. It can be easily shown. But, I don't know why I have decided that tenniskidperson3's construction produces finite sets. It was a long time ago. Sorry, apparently it was my fault. Maybe somehow I misunderstood the word "indices". Anyway, I would have put it in this way:

Let $\mathcal{B}$ be the family of all finite subsets of $\mathbb{N}$ with exactly $k$ elements. Since $\mathcal{B}$ is countable, we can construct a bijection $f: \mathcal{B} \to \mathbb{N}$ . Now, let us denote $A_k=\{j\in \mathbb{N}\mid k\in f^{-1}(j)\}\,, k\in \mathbb{N}$ and $\mathcal{A}=\{A_k \mid k\in \mathbb{N}\}$ . Apparently $\mathcal{A}$ satisfies the problem's requirement.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

366 posts

#7 h Jan 9, 2015, 1:16 AM • 3 Y

Y by nicegeo, Smoothy, Adventure10

Isn't this trivial... Just let $X$ be the set of square-free positive integers that have $k$ distinct prime divisors and let $A_i$ be the subset of $X$ that has the multiples of $p_i$ (the $i$ -th prime).

If we intersect $k$ sets, say $A_{a_1}$ , ..., $A_{a_k}$ the intersection is $\{ p_{a_1} \times ... \times p_{a_k} \}$ and if we intersect $k+1$ sets the intersection is clearly empty since we would need $k+1$ distinct prime divisors.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5 posts

HHGB

#8 h May 30, 2025, 8:46 PM

Y by

We will construct a countable set $\mathcal{A}$ . Suppose its elements (which are subsets of $\mathbb{N}$ ) are $S_1, S_2, S_3, ...$ . Let $X=\{B\subset \mathcal{A}\mid |B|=k\}$ . Since there is a bijection between $\mathbb{N}$ and $\mathbb{N}^k$ and $X$ (one can consider B ordered) is a subset of $\mathbb{N}^k$ and not having finitely many elements, there is a bijection $f$ between $\mathbb{N}$ and $X$ . For each $B \in X$ , let $f(B)$ be in all the $k$ elements of $B$ . In this construction, any $k$ distinct sets of $\mathcal{A}$ have exactly one common element by the bijection and any $k+1$ distinct sets of $\mathcal{A}$ have void intersection, because each $k$ sets of them have a unique common element.

This post has been edited 4 times. Last edited by HHGB, May 30, 2025, 8:51 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1484 posts

math90

#9 h May 31, 2025, 1:39 PM

Y by

Let $B\subset\mathbb N$ be the subset of all positive integers whose binary representation consists of exactly $k$ ones.

We will define subsets $A_1,A_2,\ldots$ in a way $A_n\subset B$ is the subset of all positive integers where $1$ appears in the $n$ -th digit from the right. Then
$\bigcap_{i=1}^n A_{a_i}=\left\{\sum_{i=1}^n2^{a_i-1}\right\}$ and all such singletons are pairwise distinct, hence every $k+1$ sets have an empty intersection.

This post has been edited 1 time. Last edited by math90, May 31, 2025, 1:40 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a