5
$\begingroup$

A friend of yours, a Shepherd, has some sheep in his stable and you know that he put some numbers on them from $1$ to $X$ in an order to track them down. Some day, you decided to give a visit to his farm.

After talking some nonsense, you start to wonder how many sheep there are in his farm since you cannot guess by just looking. You ask and he responds back:

"Imagine that you choose $10$ sheep among all, and then you take all possible ternary sums of the sheep. When you do this, you will see that each sum will be different from each other for some $10$ sheep sets. However, if I had $1$ less sheep in total, you wouldn't get all distinct sums no matter which $10$ sheep you choose. That is how many sheep I have."

Question: How many sheep are there in his farm?

For example, if the Shepherd had said $5$ sheep instead of $10$, the answer would be $8$ since all subset ternary sums of $\left \{1,2,3,5,8 \right \}$ would be different than each other and you cannot do the same with $1$ less sheep.

$\endgroup$
  • $\begingroup$ I'm confused by the condition "if I had 1 less sheep in total, you wouldn't get all distinct sums no matter which 10 sheep you choose." If I have a set, S, and all ternary sums of S are distinct, then when I remove an element from S, all ternary sums will still be unique. If I take a 10 member subset of S, and remove a member from S, there are some 10 member subsets that will be unchanged. $\endgroup$ – Tony Ruth Sep 6 '16 at 15:52
  • $\begingroup$ @TonyRuth: If you remove an element from your chosen subset S (of 10 sheep), you must replace it with another sheep from the herd; the original 9 might still be ternary-sum unique, but the addition of the new 10th will break the rule. $\endgroup$ – Ian MacDonald Sep 6 '16 at 17:05
  • $\begingroup$ Now that this has an accepted answer, what's the trick which makes it a puzzle rather than a computational task? $\endgroup$ – Peter Taylor Sep 8 '16 at 6:22
6
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Definitely a bug in my code then! $\endgroup$ – Jonathan Allan Sep 4 '16 at 17:47
  • $\begingroup$ @JonathanAllan, can you explain, why a solution with $k$ as the larger number results the number of sheep being $k+1$? Why isn't the latter $k$ as well? $\endgroup$ – elias Sep 4 '16 at 20:17
  • 1
    $\begingroup$ I get a lower bound of 114, assuming that one of the minimal sets for a given size begins $(1,2,3,\ldots)$ (which is true at least up to $n=9$). With no assumptions, I get a lower bound of 87 before running out of memory. $\endgroup$ – 2012rcampion Sep 5 '16 at 0:21
  • 1
    $\begingroup$ @elias Basically I just create a list of all valid sets starting with $\{1\}$, storing the pairwise and three-way sums for each set (e.g. $\{1,2,3\}$ is stored as the tuple $(\{1,2,3\},\{3,4,5\},\{6\})$). Adding a new $x$ to a set $(s_1,s_2,s_3)$ is then just $(s_1\cup\{x\},s_2\cup(x+s_1),s_3\cup(x+s_2)\})$. I do a sorted merge for the unions to detect duplicates. If $s_3$ has duplicates I discard the new set; if $s_2$ has duplicates I examine the set but don't store it, since it can't be a 'seed' for a new set. I add larger $x$ until $|s_1|\ge 10$ or I run out of memory. $\endgroup$ – 2012rcampion Sep 5 '16 at 7:28
  • 1
    $\begingroup$ @elias Jonathan's is a depth-first search that searches from large $x$ downward; mine is a breadth-first search that searches from small $x$ upward. $\endgroup$ – 2012rcampion Sep 5 '16 at 8:32
-2
$\begingroup$

Is it related to pattern recognition. Because I think it's not that straight forward. Still I wanna try

{1,2,3,5,8,13,21,34,55,89} Answer is 89

EDIT: Since I know that I am wrong. Here is my second attempt

Till 5 numbers it was alright to follow the fibonacci series. But as soon as we require a 6th number then the logic fails because in fibonacci series (T1 + T2) + T6 = T3 + (T4 + T5). So I've to try out a different logic henceforth.

So I thought, if our new number is greater than the sum of the max 3 values, then It will suffice So I concluded that the 6th number must be > 16(3+5+8) and hence it must be 17. So I got a new sequence : {1,2,3,5,8,17,31,57,106,195}.

But still, I was not convinced, I wanted to optimise it further. Let's assume the 6th number is X. So what we really need to achieve is (X+1+2) > (3,5,8) => X>13 => X=14 since we want smallest. Therefore moving further with rest of the remaining numbers I got another sequence : {1,2,3,5,8,14,25,45,82,150}.

Still optimising it, I guess there exists a better solution

$\endgroup$
  • 1
    $\begingroup$ Nope. 1+2+13 = 8+5+3 $\endgroup$ – astralfenix Sep 5 '16 at 12:48
  • $\begingroup$ Ohh that way... got ur point, will update shortly $\endgroup$ – Tejasva Dhyani Sep 5 '16 at 12:50
  • $\begingroup$ OK guys I got my mistake... should I remove this post to avoid any downvotes ?? $\endgroup$ – Tejasva Dhyani Sep 6 '16 at 7:36
  • $\begingroup$ Maybe you should edit it, adding how you arrived to this conclusion, and that you are aware it is not the correct solution. I think it can be turned into a good answer, as it was my first idea, and I've also seen it from other users before, so if you manage to turn it into an 'avoid this pitfall' kind of message, it can be helpful. $\endgroup$ – elias Sep 6 '16 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.