The answer is
$114$ sheep.
Because
I searched for the existence of sets of $10$ sheep (non-negative integers) such that they have all $3\text{-}subset\text{-}sums$ distinct. I first worked my way down looking for sets with any sheep up to a maximum of one less then a current upper bound (starting with an upper bound of 140 due to this OEIS sequence - see the very bottom of this answer). This actually got slower as it worked it's way down even though the space was being reduced, since there were less solutions to find at each level.
@elias pointed out that I could skip from a $116$ solution to the $114$ solution:
$\{1,6,16,30,54,72,92,112,113,114\}$
(while I was still searching at $114$) by subtracting $2$ from each of a previous upper bound output of $\{3,8,18,32,56,74,94,114,115,116\}$ from my solver (and that $1$ must be a member of the set being sought since we could always subtract a constant term from each sheep in any other satisfying set).
I then restricted my downward search to only sets containing the two sheep $1$ and $113$ to restrict the space further. I found no such solution, so finally I searched for any set containing $1$ and no number $\gt 112$, and again I found no solution. The last two searches both ran overnight on a single core.
I used this Python code:
(Or slightly less formal variations of it. It's probably not the most efficient method - but it does not require huge amounts of memory like other approaches might):
from itertools import combinations
def iterSolutions(curVals, curSums, stop=0, step=-1):
if len(curVals) == 10:
yield curVals
else:
for n in range(curVals[-1]+step, stop, step):
newSums = set()
for c in combinations(curVals, 2):
m = sum(c)+n
if m in curSums or m in newSums:
break
newSums.add(m)
else:
for solution in iterSolutions(curVals + [n], curSums|newSums, stop, step):
yield solution
I first ran the solver (a bit) like this (cm
being the largest sheep number in a set currently being sought):>>> cm = 139
>>> while 1:
... for sln in iterSolutions([cm], set([])):
... print(sln)
... cm -= 1
... break
... else:
... print("No solutions found at cm = ".format(cm))
... break
in it's current form the above code will find the final solution within an hour, but wont find the $\{116,...,3\}$ set shown above. It will then keep searching at cm=113
for some very long amount of time, find no solutions and print No solutions found at cm = 113
. To skip using the same method, one could run the modification below instead, it will skip checks at cm: 138-130, 127, 124, 123, 121-117,
and 115
, but it will still run for cm=113
for just as long:>>> cm = 139
>>> while 1:
... for sln in iterSolutions([cm], set([])):
... print(sln)
... subtract = sln[-1] - 1
... if subtract > 0:
... adjustedSln = [v - subtract for v in sln]
... print(adjustedSln)
... cm = adjustedSln[0]
... cm -= 1
... break
... else:
... print("No solutions found at cm = ".format(cm))
... break
Next I searched for a set containing $1$ and $113$ like so:>>> for sln in iterSolutions([113, 1], set([]), 113, 1)
... print(sln)
... else:
... print("Done")
which ran overnight, and finished, finding no solution with sheep $1$ and $113$ in the set and all others in between.
The final step was then to run it like this:>>> for sln in iterSolutions(1, set([]), 113, 1):
... print(sln)
... else:
... print("Done")
which also ran overnight and found no solution with sheep $1$ in the set and all others less than $113$ - so the shepherd would have $113$ sheep if he had $1$ less sheep, hence he has $114$ sheep.
Reduced bounds from before I started a search...
Greater than $8$ (well, $10$ hehe) and less than or equal to $309$
Because
No subsets (even of cardinality $2$) of the set
$\{148,225,265,285,296,302,305,307,308,309\}$
have equal sums (source: OEIS)
A lower value for the upper bound is:
$278$, since the set $\{1,2,4,8,15,28,52,96,165,278\}$ has all $120$ $3\text{-}subset\text{-}sums$ distinct.
Lowered further by @astralfenix to
$150$ due to the existence of the set $\{1,2,3,5,8,14,25,45,82,150\}$
This can be lowered a touch to
$140$ due to the existence of the set $\{1, 2, 3, 5, 8, 14, 25, 45, 82, 140\}$
This is the set of the smallest $10$ non-negative integers yielded by starting with $\{1,2,3\}$ and adding the next possible integer that keeps the set distinct with all $pairwise\text{-}sums$ distinct; and all $3\text{-}subset\text{-}sums$ distinct (Source: OEIS)