Partitioning A Formula

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Ddanndt
Posts: 60
Joined: Fri Oct 02, 2009 4:18 pm UTC
Location: Paris

Partitioning A Formula

Postby Ddanndt » Mon Mar 28, 2011 11:30 am UTC

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?"
God does not care about our mathematical difficulties — He integrates empirically.
—Albert Einstein

User avatar
Lothar
Posts: 63
Joined: Sat Dec 23, 2006 11:37 am UTC
Location: Berlin, Germany
Contact:

Re: Partitioning A Formula

Postby Lothar » Mon Mar 28, 2011 12:50 pm UTC

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.
Always program as if the person who will be maintaining your program is a violent psychopath that knows where you live.

If you're not part of the solution, you're part of the precipitate.

1+1=3 for large values of 1.

TPressey
Posts: 6
Joined: Wed Aug 18, 2010 11:49 pm UTC

Re: Partitioning A Formula

Postby TPressey » Mon Mar 28, 2011 1:17 pm UTC

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?

User avatar
Adacore
Posts: 2755
Joined: Fri Feb 20, 2009 12:35 pm UTC
Location: 한국 창원

Re: Partitioning A Formula

Postby Adacore » Mon Mar 28, 2011 3:34 pm UTC

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.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Partitioning A Formula

Postby Yakk » Mon Mar 28, 2011 3:45 pm UTC

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.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Partitioning A Formula

Postby WarDaft » Mon Mar 28, 2011 7:54 pm UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Partitioning A Formula

Postby skullturf » Sun Apr 03, 2011 3:25 am UTC

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
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland

Re: Partitioning A Formula

Postby EricH » Mon Apr 04, 2011 8:11 pm UTC

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.
Last edited by EricH on Tue Apr 05, 2011 7:08 pm UTC, edited 1 time in total.
Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Partitioning A Formula

Postby skullturf » Mon Apr 04, 2011 9:38 pm UTC

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
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: Partitioning A Formula

Postby Ankit1010 » Tue May 03, 2011 8:17 am UTC

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)

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Partitioning A Formula

Postby phlip » Tue May 03, 2011 9:06 am UTC

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 nCk-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.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 13 guests