Proof about logarithms

Revision en2, by snorkel, 2021-04-09 01:35:50

Given numbers $$$1$$$ to $$$n$$$, we have to make all those number equal to zero by choosing some subset and subtracting same value from all of them, we have to use minimum number of operations.

My idea was to always split it into two parts and get two {$$$1,2..n/2-1,n/2$$$} sets from {$$$1,2,..n$$$} set and continue like this recursively. This approach is correct and leads to $$$ceil(log_2(n))$$$ solution. What is the proof this being optimal?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English snorkel 2021-04-09 01:35:50 2 Tiny change: 'tracting some value f' -> 'tracting same value f'
en1 English snorkel 2021-04-09 00:43:00 454 Initial revision (published)