Previous in Permutation and Combination Next in Permutation and Combination
Question Number 218445 by mr W last updated on 10/Apr/25
$${there}\:{are}\:\mathrm{100}\:{students}\:{in}\:{a}\:{school}. \\ $$$${it}\:{is}\:{found}\:{out}\:{that}\:{each}\:{student}\: \\ $$$${should}\:{select}\:{at}\:{least}\:\mathrm{4}\:{courses},\:{so}\: \\ $$$${that}\:{no}\:{two}\:{students}\:{have}\:{the}\:{same}\: \\ $$$${selection}.\: \\ $$$${how}\:{many}\:{different}\:{courses}\:{does}\: \\ $$$${the}\:{school}\:{offer}? \\ $$
Answered by MrGaster last updated on 10/Apr/25
![C:∪_(k=4) ^v ((([v])),(k) )⊇{S_i }_(i=1) ^(100) ,S_i ⊆[v],∣S_i ∣≥4,S_i ≠S_j ∀i≠j min v s.t∣∪_(k=4) ^v ((([v])),(k) )∣≥100 ⇒Σ_(k=4) ^v ((v),(k) )≥100 Lower bound via ((v),(4) )≤Σ_(k=4) ^v ((v),(4) )<2^v ((v),(4) )=((v(v−1)(v−2)(v−3))/(24))≥100 ⇒v(v−1)(v−2)(v−3)≥2400 Test v=9: 9×8×7×6=3024≥2400 Test v=8: 8×7×6×5=1680<2400 ⇒ determinant ((9))](Q218449.png)
$$\mathbb{C}:\underset{{k}=\mathrm{4}} {\overset{{v}} {\cup}}\begin{pmatrix}{\left[{v}\right]}\\{{k}}\end{pmatrix}\supseteq\left\{\mathcal{S}_{{i}} \right\}_{{i}=\mathrm{1}} ^{\mathrm{100}} ,\mathcal{S}_{{i}} \subseteq\left[{v}\right],\mid\mathcal{S}_{{i}} \mid\geq\mathrm{4},\mathcal{S}_{{i}} \neq\mathcal{S}_{{j}} \forall{i}\neq{j} \\ $$$$\mathrm{min}\:{v}\:\mathrm{s}.\mathrm{t}\mid\underset{{k}=\mathrm{4}} {\overset{{v}} {\cup}}\begin{pmatrix}{\left[{v}\right]}\\{{k}}\end{pmatrix}\mid\geq\mathrm{100} \\ $$$$\Rightarrow\underset{{k}=\mathrm{4}} {\overset{{v}} {\sum}}\begin{pmatrix}{{v}}\\{{k}}\end{pmatrix}\geq\mathrm{100} \\ $$$$\mathrm{Lower}\:\mathrm{bound}\:\mathrm{via}\:\begin{pmatrix}{{v}}\\{\mathrm{4}}\end{pmatrix}\leq\underset{{k}=\mathrm{4}} {\overset{{v}} {\sum}}\begin{pmatrix}{{v}}\\{\mathrm{4}}\end{pmatrix}<\mathrm{2}^{{v}} \\ $$$$\begin{pmatrix}{{v}}\\{\mathrm{4}}\end{pmatrix}=\frac{{v}\left({v}−\mathrm{1}\right)\left({v}−\mathrm{2}\right)\left({v}−\mathrm{3}\right)}{\mathrm{24}}\geq\mathrm{100} \\ $$$$\Rightarrow{v}\left({v}−\mathrm{1}\right)\left({v}−\mathrm{2}\right)\left({v}−\mathrm{3}\right)\geq\mathrm{2400} \\ $$$$\mathrm{Test}\:{v}=\mathrm{9}:\:\mathrm{9}×\mathrm{8}×\mathrm{7}×\mathrm{6}=\mathrm{3024}\geq\mathrm{2400} \\ $$$$\mathrm{Test}\:{v}=\mathrm{8}:\:\mathrm{8}×\mathrm{7}×\mathrm{6}×\mathrm{5}=\mathrm{1680}<\mathrm{2400} \\ $$$$\Rightarrow\begin{array}{|c|}{\mathrm{9}}\\\hline\end{array} \\ $$
Commented by mr W last updated on 10/Apr/25
��
Answered by mr W last updated on 10/Apr/25
$${say}\:{the}\:{school}\:{offers}\:{n}\:{courses}. \\ $$$${C}_{{n}} ^{\mathrm{4}} \geqslant\mathrm{100}\:\wedge\:{C}_{{n}} ^{\mathrm{3}} <\mathrm{100} \\ $$$$\Rightarrow{n}=\mathrm{9} \\ $$
Answered by Spillover last updated on 12/Apr/25
n!/4!/(n-4)!=100 n!/(n-4)!=2400 n(n-1)(n-2)(n-3)=2400 8<n<9 N=9