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}⊆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}⊆A⇒|A|≥2, 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 ≤8: Suppose there can be only 8 numbers. And suppose they are 1,p1,p2,p3,p4,p5,p6,100. Then 100≤2p6≤4p5≤8p4≤16p3≤32p2≤64p1≤128. It's obvious that p1=2, then p2≤4. But 32p2≥100, then p2=4. Similarly, we get 7≤p3≤8. But p3 can't be 7 because of the rule. So p3=8. Then, 13≤p4≤16. And also get p4=16. Then, 25≤p5≤32. And get p5=32. Finally, we can't find a p6 that satisfy all the rules. Thus, the least possible cardinality of set A is 9.◼