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 5 trên 5: Trường hợp số mũ nhỏ và kết luận

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

a_r\le100\Longrightarrow cn\le2^0+2^1+\cdots+2^{100}=n

Phân tích chi tiết

Nếu $a_r\le100$ , khai triển nhị phân dùng nhiều nhất $100$ lũy thừa được chọn từ $\{2^0,2^1,\ldots,2^{100}\}$ . Vì thế $cn\le2^0+2^1+\cdots+2^{100}=n$ . Do $cn$ là một bội dương của $n$ , đẳng thức sẽ buộc $c=1$ và đòi hỏi cả $101$ lũy thừa $2^0,\ldots,2^{100}$ đều xuất hiện, điều này không thể với biểu diễn dùng nhiều nhất $100$ lũy thừa. Mâu thuẫn này cho thấy không có bội dương nào của $n=2^{101}-1$ là hào nhoáng; kết hợp với chặn dưới, đây là số nhỏ nhất như vậy.