Partitioning A Formula

[Ddanndt]

It's a problem I've created and I'm not sure if it's solvable or not but I'll share it anyways:
"A man has discovered an important formula but knowing the whole formula endangers his life cos he can get kidnapped etc... Therefore the man decides to divide his work into 5 parts A, B , C, D and E and shares it between his 6 sons. He doesn't even trust his sons who could steal his formula so he forbids more than 2 of his sons meeting at the same place with parts of the formula. So how will he divide the parts A,B, C, D and E between his sons( of course he can share more than 1 copy of a part ) so that no 2 sons can complete the formula and so that if any 2 sons die, he can still reconstitute the original formula?"

[Lothar]

Not so difficult... a bit of case analysis. Perhaps someone can come up with a better method?

Spoiler:

There is no solution.

Clearly each son must have at least one part, for if one son didn't, then according to requirements, he and two other sons should have all of the parts among them, but as he is redundant, just the two other sons could steal the formula.

Equally clearly, no son can have four parts, otherwise he could complete the formula with any of his brothers who had the missing part, and if nobody has the missing part, the formula is impossible to reconstruct.

If a son has only one part, then since he and every pair of his brothers must have all of the parts among them, every pair of his brothers has the other parts between them. But then none of his brothers could have his part, else they would be complete without him. But then if he dies, the formula is lost. Thus all sons have at least two parts.

Also, if a son has only two parts, say A and B, then every pair of his brothers has all of B, C, and D between them. If anybody else has part A, nobody could have part B except for him, otherwise those two could team up to steal the formula. If he is the only one with part A or part B, then if he dies, the formula is lost. Thus all sons have exactly three parts.

But even if all sons have three parts, the requirements still can't be fulfilled. Suppose one son had A, B, and C. Then no other son could have both D and E, otherwise two would be enough. So WLOG, another son has A, B, and D. To complete the formula with them, all three remaining sons must have E, but then those three don't have D among them, so they could not reconstruct the formula. Therefore, there is no solution.

[TPressey]

Another interesting question would be:
Is it possible to divide SIX parts of the equation among the six sons in the manner described?

And a harder question:
What is the minimum ratio of parts to sons that would allow this problem to be solved?

[Adacore]

Generalising a bit (this is all fairly basic, but perhaps an interesting start):

Spoiler:

For number of pieces of code, N, and number of sons, S. In order to fulfil the rules, each piece of code must be in the possession of at least three sons. I can't see any reason why it would ever be optimal to have this number be greater than three, so am going to assume that each piece of code is always known by exactly three sons.

Obviously the N=1 and N=2 cases are impossible. In the N=3 case, no son can have more than one piece of the code (or a meeting could cause the code to be known), and three sons have to have each piece of code, so S=9. The solution of this case can be trivially expanded to give a viable solution for N=4 (sons 1,2,3 know A, sons 4,5,6 know B, sons 7,8,9 know C,D) with an upper bound of 9.

In the N=5 case (which is the original problem statement), it's possible with S=7. Again, the solution for N=5 can be trivially expanded to N>5, so the upper bound for all other cases is S=7. I'm pretty sure that's also the optimum for any N>4, but I don't have a proof.

My only real conclusion which I hadn't realised before starting this is that any solution for N=n can also be used for N>n.

It might get more interesting if you start varying the number of sons who can meet, M, but I suspect your minimum bound is always going to be S=2*(M+1)+1, applying for N>2*M.

[Yakk]

The problem is actually pretty easy, if you hit it with the right hammer.

Spoiler:

You give everyone (N choose 3) encrypted copies of the formula. Each encrypted with a different key. We'll call the encrypted data E_a_b_c, with N > a > b > c >= 0, and keys K_a_b_c.

For child i, the child is given all of the encrypted copies (and their indexes), and all of the keys that contain i -- ie, K_i_x_y, K_x_i_y and K_x_y_i.

To build the decryption key from 3 of the children, you find the key set that you and the other two children share. You then build the decryption key. You then apply it to the encrypted formula.

Assuming strong encryption, the above secures the formula, but requires 3 of the children to conspire to decrypt the formula.

Note that "splitting the key" could be as simple as doing 3 layers of encryption, one per child, in the proper order, and handing the child the key to do the decryption (after the other steps are done).

Extending this to k sons can live is easy.

[WarDaft]

Even easier,

Spoiler:

generate a parabola based on the formula (if of the form y = ax^2 + bx + c, encode the formula in one of a, b, or c.) Give each child a unique point chosen randomly on the parabola.

Any two children have only two points, which can only describe a line. Any three children have 3 points, and can uniquely determine the parabola, and thus recover the formula.

[skullturf]

I like the purely combinatorial problem implicit in the original post, and it might be worth exploring ways to formulate the "right" general question.

Let the "pieces of the formula" be the integers 1,2,...,n. Suppose the number of sons is k.

Definition: By a "scheme", we mean a list of k subsets of {1,2,...,n} such that
(i) the union of all k subsets is all of {1,2,...,n}, and
(ii) no two subsets have a union that's all of {1,2,...,n}.

Problem: Given n and k, find a scheme that maximizes the number of sons who can die. (If we say "x sons can die", we mean that any k-x subsets in the scheme have a union that's all of {1,2,...,n}.)

Illustrations:

If n=5 and k=5, here's a scheme where any one son can die:

{1,2} {2,3} {3,4} {4,5} {5,1}

If n=7 and k=7, here's a scheme where any two sons can die:

{1,2,3} {2,3,4} {3,4,5} {4,5,6} {5,6,7} {6,7,1} {7,1,2}

I wonder if the answer, in general, depends only on the "size" of n and k, or if there's something a bit more "algebraic" going on with connections to design theory.

Edit: Here's a scheme with n=6 and k=4 where any one son can die. (So no two sons can recreate the formula, but any three sons can recreate the formula.)

{1,2,3} {1,4,5} {2,4,6} {3,5,6}

[EricH]

Here's a scheme with n=6 & k=6 where any two sons can die:

Spoiler:

{1,2,3} {3,4,5} {3,5,6} {1,4,6} {1,2,5} {2,4,6}

And, for anyone interested, I constructed it by labeling each son with a 6 digit binary value, with the constraints that each digit should be 1 in exactly three of the six values, but no value can be the 2's complement of any other. Looking from that viewpoint, it doesn't appear to be possible to solve for n=5 & k=6. Unless, as Yakk pointed out, we use encryption to make n as large as necessary. That's not a proof, though--I haven't got time today to make sure that n=5 & k=6 is impossible.

Edit: switched k & n to make sense.

[skullturf]

I was sufficiently interested in this combinatorial problem to start writing up some general notes on it and to explore connections to other studied problems. I may post later summarizing my findings.

Edit: I didn't bother writing up my own notes, but here are the connections I noticed.

A "scheme", as I defined it, is very closely related to a "covering" in combinatorial design theory. Specifically, a 2-(v,k,1) covering. (The relationship is not instantly obvious -- the blocks of the covering are the sets of children that don't receive a particular piece of the formula.)

More about coverings

Also, this topic seems to be related to Shamir's Secret Sharing.

[Ankit1010]

I think this is simple enough to solve with lagrange interpolation. Say you have k sons and n pieces of the formula. You can use lagrange interpolation to form a curve from the n pieces, which is your secret. Then, distribute the n pieces such that any 2 sons have all n between them ( or any i sons have all n, for 1<=i<=k)

[phlip]

Spoiler:

This seems similar to this puzzle... The solution to that isn't directly usable here, though, as it depends on, in that puzzle, 5 people working together is never enough, but 6 is always enough... whereas with the OP's puzzle, it specifies that 2 is never enough and 4 is always enough... but it doesn't specify either way whether a group of 3 children is or is not enough. It's possible for a solution to have it so that some groups of 3 children have enough information, and other groups do not. Which makes that solution a little harder to solve.

However, it does give one piece of information quickly: if you wanted to allow 3 children to die and still be able to recreate the formula, ie no 2 children can solve the formula, but any 3 can, then you need a grand total of 15 pieces... assign one piece to each pair of children (of which there are 15), and then each child gets the pieces for all the pairs they are not a member of. Then every pair of children, working together, is missing exactly one piece, and every other child who could join that pair to make a group of 3 has that missing piece. Generally, if you have n children, and each group of k must be able to solve the puzzle, but each group of k-1 must not be able to solve it, you need ⁿC_k-1 pieces. But, as I said, if it's not "k" and "k-1", but "k" and "k-2", or something like that, then it becomes more complicated.