Find the least possible cardinality of a set $A$ of natural numbers, the smallest and greatest of which are $1$ and $100$, and having the property that every element of $A$ except for $1$ equals the sum of two elements of $A$.
Problem
Source:
Tags: set, algebra
10.04.2021 03:22
your posting problems faster than people can solve them
10.04.2021 07:56
Ans is $1$.
10.04.2021 07:58
It can't be $1$ since $\{1,100\}\subseteq A$.
10.04.2021 08:01
Wdym so what ? @below sorry I did not understand the problem correctly. ok solving right now.
10.04.2021 08:05
$\{1,100\}\subseteq A\Rightarrow|A|\ge2$, so $|A|$ cannot be $1$.
10.04.2021 08:18
Are u sure u are not missing something? Becoz such a set is impossible. Can u give an example of such a set ?
10.04.2021 08:20
$\{1,2,3,6,12,13,25,50,100\}$ is an example.
10.04.2021 08:23
Ahhhh....how come $2$ be expressed as a sum of two elements of the set? I see, ok trying to solve.
10.04.2021 08:25
It didn't say that the numbers need to be distinct.
10.04.2021 16:04
I found $\{1, 2 ,4, 8, 16, 32, 36, 64, 100\}$ Not sure if its the smallest, but it seems pretty optimal.
10.04.2021 16:41
The answer IS $9$. What we need to prove is that the cardinality can't be $\le 8$: Suppose there can be only $8$ numbers. And suppose they are $1,p_1,p_2,p_3,p_4,p_5,p_6,100$. Then $100\le 2p_6 \le 4p_5 \le 8p_4 \le 16p_3 \le 32p_2 \le 64p_1 \le 128$. It's obvious that $p_1=2$, then $p_2\le 4$. But $32p_2\ge 100$, then $p_2=4$. Similarly, we get $7\le p_3\le 8$. But $p_3$ can't be $7$ because of the rule. So $p_3=8$. Then, $13\le p_4\le 16$. And also get $p_4=16$. Then, $25\le p_5 \le 32$. And get $p_5=32$. Finally, we can't find a $p_6$ that satisfy all the rules. Thus, the least possible cardinality of set $A$ is $9$.$\blacksquare$