Does someone have an "natural" solution for part (b)?

See the related chapter C8 from [R.K. Guy - Unsolved Problems in Number Theory]. Using Conway & Guy sequence, we can find $\{11,17,20,22,23,24\} \mapsto \{1,22,34,40,44,46,48\}\mapsto \{1,2,44,68,80,88,92,96\}$, or directly $\{40,60,71,77,80,82,83,84\}$ as examples for point (a). For point (b), it is obvious that $10$ is not $100$-discerning, since the $2^{10} - 1 > 1000$ sums are more numerous than $10\cdot 100$, which is larger than the largest sum. To show $9$ is not $100$-discerning seems to be a much more arduous task. See http://fks.sk/~kubus/doc/201012ssd.pdf for a computation showing the least not discerning set of $9$ positive integers has largest element $161$ (the results there confirm the beginning of the Conway & Guy sequence is best). See here http://rec-puzzles.org/index.php/Subsets%20Solution, pointed at from here http://www.cut-the-knot.org/pigeonhole/subsums.shtml#solution.

I guess this lemma kills 4-(b), Since \[ 91^2 + 92^2 + \cdots + 99^2 = 81285 < \frac{4^9 - 1}{3} = 87381\]

Doesn't Pidgeonhole do the job for b? Suppose $1 \le a_1 < a_2 < \dots < a_9 \le 99$ are nine distinct natural numbers. Consider all expressions of the form $a_i - a_j + a_k - a_l$ where $9 \ge i > j > k > l \ge 1$. There are $\binom{9}{4} = 126$ different such expressions. But for such an expression, since $a_i > a_j > a_k > a_i$, we have $0 < a_i - a_j + a_k - a_l < 100$. Therefore there must be two different expressions with the same value. Let them be $a_i - a_j + a_k - a_l = a_{i'} - a_{j'} + a_{k'} - a_{l'}$. Rearrange to obtain $a_i + a_{j'} + a_k + a_{l'} = a_{i'} + a_j + a_{k'} + a_l$. But notice the sets $\{a_i,a_{j'},a_k,a_{l'}\}$ and $\{a_{i'},a_j,a_{k'},a_l\}$ are different, for if they are equal, from $a_i > a_j > a_k > a_l$ and $a_{i'} > a_{j'} > a_{k'} > a_{l'}$ we obtain, first supposing WLOG $a_i \ge a_{i'}$, that $a_i = a_{i'}$, and so on analogously $a_j = a_{j'}$, $a_k = a_{k'}$, $a_l = a_{l'}$. But this contradicts the expressions $a_i - a_j + a_k - a_l$, $a_{i'} - a_{j'} + a_{k'} - a_{l'}$ being different. So $9$ cannot be $100$-discerning.

Did you prove that those sets have four different elements? For example if $a_j'=a_k$, your argument doesn't work.

Wow, nice flaw... The idea seems reasonable though because by considering subsets of size $\binom{n}{\lfloor \frac{n}{2}\rfloor}$, we would find that if $n$ is $b$-discerning then $b \ge \binom{n}{\lfloor \frac{n}{2}\rfloor} = o(\frac{2^n}{\sqrt{n}})$, which is a known bound as one of mavropnevma's links states. But as it appears to be, the argument is not so generous...

syk0526 wrote: I guess this lemma kills 4-(b), Since \[ 91^2 + 92^2 + \cdots + 99^2 = 81285 < \frac{4^9 - 1}{3} = 87381\] Sorry for being stupid, but how is this solve the problem?

Because if 9 is 100-decreasing then if we say $ U= $ { $ a_1,a_2,...,a_9 $ } then, $ 81285=91^2+92^2+...+99^2\geq a_1^2 +...+a_9^2>\frac{4^9-1}{3}=87381 $. Done.

JuanOrtiz wrote: Did you prove that those sets have four different elements? For example if $a_j'=a_k$, your argument doesn't work. If $a_j'-a_k$, then you can remove both of them from their respective sets, to obtain that $a_i+a_j+a_l=a'_i+a'_k+a'_l$, and we have two sets of three elements each that have the same sum.

syk0526 wrote: I guess this lemma kills 4-(b), Since \[ 91^2 + 92^2 + \cdots + 99^2 = 81285 < \frac{4^9 - 1}{3} = 87381\] Just curious, what is the smallest non-1000-discerning number? 11 is 1000-discerning, (285,433,510,550,570,581,587,590,592,593,594) and 13 is not (from the above lemma). What about 12?

I heard this problem from János Pataki in the early 90's; later the problem was used in the KöMaL contest in May, 1997. My old proof for part (b) was something like this. Suppose that some integers $0<a_1<a_2<\ldots<a_9$ satisfy the property that their subsets have distinct sums. Consider all 3-, 4-, 5- and 6-subsets of $\{a_1,\ldots,a_9\}$ whose sum is between $A=a_1+a_4+a_5$ and $B=a_1+a_4+a_5+a_7+a_8+a_9$. Altogether there are $\binom93+\binom94+\binom95+\binom96=420$ sets with $3,4,5$ or $6$ elements, but a few of them, depending on the choice of $a_1,\ldots,a_9$, may give too small or too big sums. The sums $a_1+a_2+a_x$, $a_1+a_3+a_x$, $a_2+a_3+a_x$ and $a_1+a_2+a_3+a_x$ may be less than $A$, this is $7+6+6+6=25$ sets. Every other set contains at least two elements greater than $a_3$, so its sum is at least $a_4+a_5+a_1=A$. In order to count the possible too big sums, it may be reasonable to consider the complementers and count those sets that may give lower sum than $a_1+a_2+a_6$. These sets are the subsets of $\{a_1,\ldots,a_5\}$; this is $\binom53+\binom54+\binom55=16$ subsets --- their complementers may give higher sum than $B$. Every other set contains an element greater than $a_5$, so its sum is at least $a_1+a_2+a_6$. Hence, there are at least $420-20-16=384$ sets of $\{a_1,\dots,a_9\}$ whose sum is between $A$ and $B$. So, $B-A=a_7+a_8+a_9\ge 383$, and therefore $a_9 > \frac{a_9+(a_8+1)+(a_7+2)}{3} \ge \frac{383+3}3 > 128$.

Can someone please please please tell me how to solve this problem, with motivation. I don't know where in the world the above solution came from...

viperstrike wrote: Can someone please please please tell me how to solve this problem, with motivation. I don't know where in the world the above solution came from... The first idea is simply taking the largest sum, $a_1+\ldots+a_9$. There are $2^9-1=511$ distinct sums, so $a_1+\ldots+a_9\ge511$. Then we can compare all terms with $a_9$. This give something like $511\le a_9+(a_9-1)+\ldots+(a_9-8)$; $a_9\ge\frac{511+1+2+\ldots+8}9>60$. If you consider examples when the largest number is relatively small, and compute all possible sums, you will observe that the sums with using only a few terms or excluding only a few terms are sparse. This makes the estimate less effective. Moreover, the number of such sums is low. Hence, we will achieve a better bound using only sums in which roughly half of the numbers is used. For instance, we can take all sums with 3, 4, 5 or 6 terms; the lowest such sum is $a_1+a_2+a_3$, the highest is $a_4+\ldots+a_9$; the number of them is $\binom93+\binom94+\binom95+\binom96=420$; this leads to $420-1\le (a_4+\ldots+a_9)-(a_1+a_2+a_3) \le 6a_9-21$; $a_9\ge 74$. The last idea was to narrow the sums further. If we replace the difference $(a_4+\ldots+a_9)-(a_1+a_2+a_3)$ in such a way that some terms in the estimate cancel out, then we have to divide by a smaller number instead of $6$.

Here is a more motivated construction for (a) for those who don't know about the Conway & Guy sequence. We can take $\{3,6,12,24,48,97,98,99\}$. Indeed, the subset sums are $0,3,6,\ldots,93,97,98,99,\ldots,192,195,196,197,\ldots,290,294,297,300,\ldots,387$. The motivation for this is that greedy bottom up doesn't work (we get powers of 2), so we try greedy top down. We can't take 96, but we've made it so there are 4 different tiers of subset sums depending on how many numbers in $\{97,98,99\}$ we use. We should construct the other 5 such that they sum to less than 97, so there are no collisions between tiers. Furthermore, if all are divisible by 3 then we won't have collisions within tiers as long as there are no collisions in the bottom tier. The rest of the set follows.

Does the following sequence work for a? $\{66,79,87,92,95,97,98,99\}$

Well I dont know but it should be easy to check with a bit of coding

cosinechicken wrote: Does the following sequence work for a? $\{66,79,87,92,95,97,98,99\}$ No, $87 + 98 + 99 = 92 + 95 + 97$. I think the following is a valid construction: $\{53,75,86,92,95,97,98,99\}$

If we start from below with $1$, the best condition we have is $\{1,2,4,8,16,32,64 \}$ which has $7$ members and we can't add one more since we wont miss any sums from $1-99$. Therefore, one may try the same idea from starting $99$. Hence, $\{ 99,98,97,48,24,12,6,3\}$. ( We basically select elements such that new sums don't occupy new possible elements i.e$ a_1+a_2>100$, that is why starting from $99,98$ is more efficient than $1,2$)One may manually check that this indeed works, or use python

For $(b)$, my idea is quite similiar as post #5. FTSOC let such integers be $a_1,a_2,...,a_9$. Observe the expression $a_i-a_j+a_k-a_l$ where $i >j>k>k$. We have 126 such different expressions while our expression is at most 99, hence there exists two expressions with same value i.e $\{ a_i,a'_j,a_k,a'_l \} , \{a'_i,a_j,a'_k,a_l \}$. If $a_i= a'_i$ we can remove the elements and now we will have 3 sized subsets, if $a'_j=a_j$, or etc, we can do chain argument to either these sets are equal or we have two different sets, contradiction. If $a_i=a_j'$, we have $$2a_i+a_k+a'_l=a'_i+a_j+a'_k+a_l \Rightarrow a_i+a'_l>a'_i+a'_k$$Since we have $a'_k>a_l$, we must have $a'_i<a_i=a'_j$, contradiction. Hence this case is impossible. Other cases are similiar. Hence, we have shown that $n=9$ is impossible.

For construction part $a$, simply take the lovely construction: $35, 55, 65, 71, 74, 76, 77, 78$. This follows from a recursive construction to get from $n$ to $n+1$, we add ${n \choose \lfloor n/2 \rfloor}$ to the set, and scale up every previous term by this value. The idea is that this construction maintains an order of all of its sums: ordered first by the number of summands, then tiebroken by whether the set has the newest term, then second newest, etc. Now to finish part $b$, consider the variance of a random variable $X$ chosen by picking a sum of subset at random from the set $\{x_1, x_2, \ldots, x_9\}$. It is the sum of independent random variables choosing the include a given element with a $50\%$ chance each. We have that: $\textrm{Var}(X) \leq \frac{99^2+98^2+\ldots+91^2}{4}$ and since $X$ never has two possibilities hitting the same value and takes $512$ different values, we have: $\textrm{Var}(X) \geq \frac{2(1^2 + 2^2 + \ldots + 255^2)}{512} = \frac{255 \cdot 511}{6}$ Now combining the inequalities, we have $243855 \geq 260610$. This is a contradiction, so we are done. Edit: Yeah @below, I'm trimming the two terms that are within $1$ of the mean and bounding everything else strictly below. It's easier to compute than $1^2 + 3^2 + \ldots$ and is enough so why not.

Inconsistent wrote: since $X$ never has two possibilities hitting the same value and takes $512$ different values, we have: $\textrm{Var}(X) \geq \frac{2(1^2 + 2^2 + \ldots + 255^2)}{512} = \frac{255 \cdot 511}{6}$ Now combining the inequalities, we have $243855 \geq 260610$. Am I misunderstanding something or does this only get you $$\mathrm{Var}(X) \geq \frac{2((1/2)^2+(3/2)^2+\cdots+(509/2)^2)}{512}$$which isn't large enough? Although there is probably a (messy) way to fix this with more precise estimates—I hope so, since the idea is nice. Edit: nvm the sum you had only contains 510 elements so this is fine? Edit^2: actually the sum that I wrote is big enough as well. I didn't realize that $243855 \geq 260610$ came from multiplying both sides by $12$

I suppose I will also post another construction for part (a). Take the set $\{1,22,44,85,91,95,97,99\}$. Call the last five elements large and the rest small. Suppose we had two distinct subsets with same sum and WLOG they are disjoint. Since $99+97+44+22+1<95+91+85$, they must have the same number of large elements. The absolute difference between the sums of any same-size subsets of large elements is even, nonzero (this is doable without brute force: note that large elements are $101-2F_k$ for $2 \leq k \leq 6$), and at most $99+97-91-85=20$. Thus the small parts of our two subsets (which are disjoint) must have difference equal to an even integer in $[2,20]$, but the only possible even differences are $0,22,44$.