កំណែលំហាត់សិស្សពូកែទូទាំងប្រទេសឆ្នាំ២០០៩(១១)

សំណុំ $\textrm{E}_n$ មួយមាន $n$ ធាតុ ដែល $n$ ជាចំនួនគត់វិជ្ជមាន។ តាង $\textrm{P}(\textrm{E}_n )$ ជាសំណុំនៃសំណុំរងរបស់ $\textrm{E}_n$ ហើយ $\textrm{Card}(\textrm{P}(\textrm{E}_n ))$ ជាចំនួនធាតុរបស់ $\textrm{P}(\textrm{E}_n)$ ។ តាមវិចារដោយកំណើនបង្ហាញថា

$\textrm{Card}(\textrm{P}(\textrm{E}_n))=2^n$

ចម្លើយ

ករណី $n=1$ ឧទាហរណ៍ $\textrm{E}_n=\{1\}$ នោះយើងមានសំណុំរង

$\{\O\};\{1\}$

ដូច្នេះ យើងមានសំណុំរងចំនួន $2$ ។

ករណី $n=2$ ឧទាហរណ៍ $\textrm{E}_n=\{1;2\}$ នោះយើងមានសំណុំរង

$\{\O\};\{1\};\{2\};\{1,2\}$

សំណុំទាំងនេះបានមកដោយផ្សំសំណុំរងបានមកពីករណី $n=1$ ផ្សំនឹងធាតុបន្ថែម គឺលេខ $2$ តាមរបៀប
សំណុំរងដែលមានស្រេច៖ $\{\O\};\{1\} \implies$ សំណុំរងចំនួន $2$
សំណុំរងកើតក្រោយផ្សំលេខ $2$ ចូលទៀត៖ $\{2;\O\};\{2;1\} \implies$ កើតបានសំណុំរង $2$ ទៀត។
ដូច្នេះ យើងមានសំណុំរងចំនួន $4=2^2$ ។

ករណី $n=3$ ឧទាហរណ៍ $\textrm{E}_n=\{1;2;3\}$
សំណុំរងដែលទទួលបានករណី $n=2$ : $\{\O\};\{1\};\{2\};\{1,2\} \implies$ សំណុំរងចំនួន $2^2$
សំណុំរងកើតក្រោយផ្សំលេខ $3$ ចូលទៀត៖ $\{3,\O\};\{3,1\};\{3,2\};\{3,1,2\} \implies$ កើតបានសំណុំរង $2^2$ ទៀត។
ដូច្នេះយើងទទួលបានសំណុំរងចំនួន $2^2+2^2=2^3$

សន្មតថាសំណើនេះពិតរហូតដល់ $n=k$ មានន័យថាករណី $\textrm{E}_n$ មាន $k$ ធាតុ យើងទាញបាន ចំនួនសំណុំរងស្មើ $2^k$ ។

ករណី $n=k+1$ ។ តាង $\textrm{E}_{k+1}=\{e_1,e_2,\dotsi,e_k,e_{k+1}\}$ ។ ធាតុចំនួន $k$ ដំបូងបង្កើតបានសំណុំរងចំនួន $2^k$ ។ ដោយផ្សំធាតុទី $k+1$ គឺ $e_{k+1}$ ទៅសំណុំរងទាំងនោះ យើងទាញបានសំណុំរងចំនួន $2^k$ បន្ថែមទៀត។ ដូច្នេះ សំណុំរងទាំងអស់មានចំនួន $2^k+2^k=2^{k+1}$ ។ សំណើពិត។

សម្គាល់

យើងអាចបកស្រាយសំនួរនេះតាមរបៀបងាយជាងនេះដោយមិនប្រើវិចារកំណើន។ យើងបង្កើតសំណុំរងតាមរបៀបបន្សំដូចតទៅនេះ៖
សំណុំរងដែលជាសំណុំទទេ មាន $1$
សំណុំរងមានចំនួន $1$ ធាតុ មានចំនួន $C_n^1$
សំណុំរងមានចំនួន $2$ ធាតុ មានចំនួន $C_n^2$
…..
សំណុំរងមានចំនួន $n$ ធាតុ មានចំនួន $C_n^n$