Maths Olympiad Prep

Library / /332 of 520

Combinatorics Difficulty 7.0 National olympiad Find the answer

2. 44c144 \quad c \geqslant 1 is a fixed positive integer. For each non-empty subset AA of the set {1,2,,n}\{1,2, \cdots, n\}, a positive integer ω(A)\omega(A) is assigned from the set {1,2,,c}\{1,2, \cdots, c\}, satisfying
ω(AB)=min(ω(A),ω(B))\omega(A \cap B)=\min (\omega(A), \omega(B))

where A,BA, B are any two non-empty intersecting subsets of {1,2,,n}\{1,2, \cdots, n\}. If there are a(n)a(n) such assignment methods, compute
limna(n)n\lim _{n \rightarrow \infty} \sqrt[n]{a(n)}

A number or a short expression. Spacing and $ signs are ignored.

Solution

[Solution] When c=1c=1, it is obvious that a(n)=1a(n)=1, thus we have
limna(n)n=1\lim _{n \rightarrow \infty} \sqrt[n]{a(n)}=1

Now consider the case when c2c \geqslant 2.
The set {1,2,,n}\{1,2, \cdots, n\} has 2n12^{n}-1 non-empty subsets, and these 2n12^{n}-1 non-empty subsets form the domain of the function ω(A)\omega(A).
 Let bk={1,2,,k1,k+1,,n}={1,2,,n}{k},(k=1,2,,n)\text { Let } \begin{aligned} b_{k} & =\{1,2, \cdots, k-1, k+1, \cdots, n\} \\ & =\{1,2, \cdots, n\}-\{k\},(k=1,2, \cdots, n) \end{aligned}

Let D={1,2,,n}D=\{1,2, \cdots, n\}
First, we prove that if ω(b1),ω(b2),,ω(bn),ω(D)\omega\left(b_{1}\right), \omega\left(b_{2}\right), \cdots, \omega\left(b_{n}\right), \omega(D) these n+1n+1 values are determined, then for any non-empty subset AA of DD, ω(A)\omega(A) is also determined.

We use mathematical induction.
From the given conditions, we know that when AA is an (n1)(n-1)-element subset of DD, ω(A)\omega(A) is determined.
Assume that when AA is an (nk)(n-k)-element subset of DD, ω(A)\omega(A) is determined, then when AA is an (nk1)(n-k-1)-element subset, take an element mm from DD that does not belong to AA, then B=A{m}B=A \cup\{m\} is an (nk)(n-k)-element subset of DD, by the induction hypothesis ω(B)\omega(B) is determined. Then by
A=BbmA=B \cap b_{m}

we get
ω(A)=min{ω(B),ω(bm)}\omega(A)=\min \left\{\omega(B), \omega\left(b_{m}\right)\right\}

Therefore, ω(A)\omega(A) is also determined.
By the principle of mathematical induction, the function ω\omega is completely determined by the n+1n+1 values ω(b1),ω(b2),,ω(bn),ω(D)\omega\left(b_{1}\right), \omega\left(b_{2}\right), \cdots, \omega\left(b_{n}\right), \omega(D).

Notice that each of these n+1n+1 values can take at most CC different values, so the number of ways to choose the function ω\omega is
a(n)Cn+1a(n) \leqslant C^{n+1}

On the other hand, for any of the CnC^{n} ways to choose the nn values ω(b1),ω(b2),,ω(bn)\omega\left(b_{1}\right), \omega\left(b_{2}\right), \cdots, \omega\left(b_{n}\right), we can take
ω(D)=max{ω(b1),ω(b2),,ω(bn)}\omega(D)=\max \left\{\omega\left(b_{1}\right), \omega\left(b_{2}\right), \cdots, \omega\left(b_{n}\right)\right\}

which satisfies the given conditions, thus providing a way to choose the function ω\omega. Therefore, the number of ways to choose the function ω\omega is
Cna(n)C^{n} \leqslant a(n)

Thus, we have
Cna(n)Cn+1C^{n} \leqslant a(n) \leqslant C^{n+1}

Taking the nn-th root, we get
Ca(n)nC1+1nC \leqslant \sqrt[n]{a(n)} \leqslant C^{1+\frac{1}{n}}

Taking the limit, we get
Climna(n)nlimnC1+1nC \leqslant \lim _{n \rightarrow \infty} \sqrt[n]{a(n)} \leqslant \lim _{n \rightarrow \infty} C^{1+\frac{1}{n}}

which gives
limna(n)n=C\lim _{n \rightarrow \infty} \sqrt[n]{a(n)}=C

Naturally, the above equation also holds when C=1C=1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.