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 4 trên 5: Trường hợp số mũ lớn cho phản ví dụ tối thiểu

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

cn=2^{a_1}+\cdots+2^{a_r},\ r\le100,\ a_r\ge101\Longrightarrow 2^{a_r}=2^{a_r-101}n+2^{a_r-101}

Phân tích chi tiết

Giả sử phản chứng rằng một bội $cn$ của $n=2^{101}-1$ là số hào nhoáng. Gộp các lũy thừa lặp lại bằng phép nhớ nhị phân, ta được biểu diễn bằng nhiều nhất $100$ lũy thừa phân biệt; chọn biểu diễn này với $c$ nhỏ nhất và gọi $a_r$ là số mũ lớn nhất. Nếu $a_r\ge101$ thì $2^{a_r}=2^{a_r-101}n+2^{a_r-101}$ , nên thay $2^{a_r}$ bằng $2^{a_r-101}$ làm giảm $cn$ đi $2^{a_r-101}n$ , cho một bội dương nhỏ hơn của $n$ với nhiều nhất $100$ lũy thừa nhị phân, mâu thuẫn với tính nhỏ nhất của $c$ .