Bài 2

Một số nguyên dương được gọi là hào nhoáng nếu nó có thể viết dưới dạng

2^{a_1}+2^{a_2}+\cdots+2^{a_{100}}

, trong đó

a_1,a_2,\ldots,a_{100}

là các số nguyên không âm không nhất thiết phân biệt. Tìm số nguyên dương nhỏ nhất

n

sao cho không có bội số nào của

n

là số hào nhoáng.

Bước 2 trên 5: Mọi

k

nhỏ hơn đều có bội hào nhoáng

Bước trước Bước tiếp

2^s k=2^{a_1+s}+\cdots+2^{a_r+s},\quad s=100-r;\quad 2^j=2^{j-1}+2^{j-1}\text{ increases the number of powers by one}

Phân tích chi tiết

Trước hết nhân khai triển nhị phân của $k$ với $2^s$ , trong đó $s=100-r$ . Nếu $s=0$ thì ta đã có tổng đúng $100$ lũy thừa của hai. Nếu $s>0$ , liên tiếp tách một số hạng theo $2^j=2^{j-1}+2^{j-1}$ , mỗi lần chọn một số hạng có số mũ dương; bắt đầu từ số hạng $2^{a_r+s}$ , có thể làm như vậy $s$ lần và tăng số số hạng từ $r$ lên $r+s=100$ mà không đổi giá trị. Do đó $k$ có một bội hào nhoáng, nên số $n$ nhỏ nhất không có bội hào nhoáng phải thỏa $n\ge2^{101}-1$ .