On March 30 2011 04:06 EsX_Raptor wrote:
For those who do not understand how the Hamming Code works, here is a simplified and illustrative explanation in terms of the problem stated.

For simplification purposes, let us use 8 bits of data instead of 100,000.

Suppose the following is our data:

Suppose the following is the erroneous bit:

Since we have 8 bits of data, we will need ceiling(log2(8)) + 1 = 4 agents to diagnose it. Furthermore, the agents are labeled with numbers that are powers of 2.

Every agent checks certain bits based on their number. Here are the bits each checks:

From these images, it is easy to observe that agents 1 and 4 will die upon checking the faulty bit:

Therefore, bit 1 + 4 = 5 is the faulty bit:

---

By the way, for 100,000 bits, 18 agents are necessary--not 17.

QED

just to point out your error: the +1 agent is in fact not needed: Suppose the eighth of your bits would be the faulty one, then agents 1 through 3 would all survive, leaving bit 8 as the only possible solution for the broken bit.

The only thing achieved by your +1 agent is to prove, that the remaining bit is actually broken. But if you already know, that exactly one is broken, you don't need to sacrifice an agent just to prove that.

therefore, ceiling(log2(n)) is sufficient which is 17 for 100000 as i pointed out in the first reply ;P

EsX_Raptor

United States2802 Posts

March 30 2011 00:34 GMT

#45

On March 30 2011 08:57 MisterD wrote:
just to point out your error: the +1 agent is in fact not needed: Suppose the eighth of your bits would be the faulty one, then agents 1 through 3 would all survive, leaving bit 8 as the only possible solution for the broken bit.

The only thing achieved by your +1 agent is to prove, that the remaining bit is actually broken. But if you already know, that exactly one is broken, you don't need to sacrifice an agent just to prove that.

therefore, ceiling(log2(n)) is sufficient which is 17 for 100000 as i pointed out in the first reply ;P

Brilliant! XD

THE_DOMINATOR

United States309 Posts

March 30 2011 04:22 GMT

#46

On March 30 2011 03:39 Kazius wrote:

Show nested quote +

Unfortunately, you're wrong. Just off the top of my head, have 16 search the first half in the first hour, if they found it, great. If they didn't, the 16 can find it in the next hour in the other half. Already one agent less.

BTW: After giving it 5 minutes of thought (and thanks to my Prof. for Discrete mathematics), I have the correct answer. PM me if you want a spoiler.

In mine no one dies

Kiarip

United States1835 Posts

March 30 2011 07:53 GMT

#47

OK.

If you divide 100000 bits into 21 areas, such that the intersection of any 7 is only 1 bit (this works out, because 21C7 > 100000,) then you only need 20 checks total. The most that can die without giving away the bit is 6, so you only need 13 total (13 + (13-6) = 20)

Still not as good as 11 =\. And since 7 die, you'll need at least 20 to do it twice.

BUUUT!

new solution for B!!!

16!

The first check goes as follows:

break up the set of all bits in to 29 subsets, such that the intersection of any 5 is only a single bit (and all of the bits resulting in intersections of different subsets are distinct, this is possible because 29C5 = 118 755 > 100000.)

Have 16 agents. First hour the first 16 check. At maximum 5 can die. If 5 do die, then you already know the faulty bit. If 4 die, you will need to do 12 more checks (you don't need to check the last section, because you know that a total of only 5 will cause agents to die, so if only 4 agents die you know the last one also contains the faulty bit.)

16 - 4 = 12 so even in the worst case you have enough to do the 12 more checks necessary.
At most 5 agents will die total, so you will always have 11 to complete the second check using the base-3 method posted earlier.

Kazius

Israel1456 Posts

April 01 2011 03:23 GMT

#48

Was gone for a while (more work?), but have managed to solve it. Very similar to Kiarip's solution here, but a tad more formal (and explaining why 29 and 5 are the necessary numbers).

Part A: 11 (question is equivalent to the number of bits required for representing a number between 1 and 100000 in base 3). Simple enough, and a satisfactory explanation has been given.

Part B:
1) Let there be a division of the 100000 bits into M groups, so that each N groups overlap in one bit. N will be the amount of agents killed, as N groups will overlap on the faulty bit.

Requirements:

A) M choose N must be greater than or equal to 100000. Otherwise, there is not enough information to be sure of the location of the faulty bit.
B) M-1 groups will have to be checked. If there is one death too little, we know that it is in the unchecked group, so that is equivalent to a check as well. Any less checks will allow two groups to be unchecked, and hence locating the faulty bit will not be assured.

2) There must be 11 + N agents, because 11 must survive, and up to N will die (N groups with the faulty bit may be checked).

3) The minimum amount of groups checked: All agents (11 + N) in the first check, 12 agents (11+1) in the second check (if all five die in the first check, it is located, otherwise, 12 or more remain for the second check).

4) Due to 1B, 2 and 3: M-1 = 11 + N + 12
Hence: M = 24 + N

5) Due to 1 and 4: the question can now be phrased thusly: what is 11+N, when N is the minimal natural number in which (24 + N choose N) is greater than or equal to 100000?

6) Calculation: N is 5.

Result: There must be at least 16 (11+5) agents in the first check in order to positively locate the faulty bit in 2 hours, with a minimal amount of agents left in order to complete a second check.