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?"

## Partitioning A Formula

**Moderators:** jestingrabbit, Moderators General, Prelates

### Partitioning A Formula

God does not care about our mathematical difficulties — He integrates empirically.

—Albert Einstein

—Albert Einstein

### Re: Partitioning A Formula

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

**Spoiler:**

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.

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

1+1=3 for large values of 1.

### Re: Partitioning A Formula

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?

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?

### Re: Partitioning A Formula

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

**Spoiler:**

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

### Re: Partitioning A Formula

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

**Spoiler:**

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.

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

### Re: Partitioning A Formula

Even easier,

**Spoiler:**

All Shadow priest spells that deal Fire damage now appear green.

Big freaky cereal boxes of death.

### Re: Partitioning A Formula

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}

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}

### Re: Partitioning A Formula

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

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.

**Spoiler:**

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.

### Re: Partitioning A Formula

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.

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.

### Re: Partitioning A Formula

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
- Restorer of Worlds
**Posts:**7569**Joined:**Sat Sep 23, 2006 3:56 am UTC**Location:**Australia-
**Contact:**

### Re: Partitioning A Formula

**Spoiler:**

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};`

void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}

### Who is online

Users browsing this forum: No registered users and 10 guests