Tổ hợp TST Nam Định 2020 và Biểu diễn nhị phân

2021/03/19 08:22

#tổ hợp

Bài toán. (Nam Định TST 2020) Cho tập X={22k0k2020,kN}X=\left \{ 2^{2^k}|0 \leq k \leq 2020, k\in \mathbb{N}\right \}. Xét tất cả các tập con khác rỗng của XX. Mỗi tập con AA như thế ta lấy tích của các phần tử gọi là xAx_A tính AXxA\sum_{A \subset X} x_{A}.

Ý tưởng.

Ta để ý khi lấy tích các phần tử của một tập con AA khác rỗng bất kì của XX thì xAx_{A} sẽ có giá trị là 2t2^t với tt là tổng của các luỹ thừa cơ số 22 với số mũ đôi một phân biệt. Điều này làm ta nghĩ tới biểu diễn nhị phân của một số tự nhiên.

– Con Heo’s solution –

Lời giải.

Với mỗi tập AXA \subset X khác rỗng, ta có thể viết tập AA lại thành

A={ak22kak{0;1},0k2020}A=\left \{ a_k 2^{2^k}|a_k \in \left \{ 0;1 \right \},0 \leq k \leq 2020 \right \}.

Khi đó xA=2k=02020ak2kx_A=2^{\sum ^{2020}_{k=0} a_k 2^k}.

Nhận thấy k=02020ak2k\sum ^{2020}_{k=0} a_k 2^k chính là một biểu diễn nhị phân của một số tự nhiên mm bất kì từ 11 đến 2202112^{2021}-1.

Như vậy

AXxA=ai{0;1}2k=02020ak2k=m=12202112m=2220212\sum _{A \subset X} x_A= \sum_{a_i \in \left \{ 0;1 \right \}} 2^{\sum ^{2020}_{k=0} a_k 2^k} = \sum ^{2^{2021} -1}_{m=1} 2^m = 2^{2^{2021}}-2.

Quay trở về Blog