|
This is NOT for school or anything like that, I simply found it online and want to know if anyone here can solve it.
I have not solved it yet.
Ponder This Challenge:
A spaceship has 100,000 bits of storage, and one of these bits is known to be faulty. You can locate the faulty bit using agents that run on any given subset of bits and return "OK" if all of the bits are good and die if they encounter the faulty bit. It takes an agent one hour to run a query, regardless of the size of the subset, but an infinite number of agents can run simultaneously. You need to find the wrong bit in two hours.
Since we must decide, in advance, how many agents to send with the spaceship, we are interested in the following questions:
A. What is the minimal number of agents needed? (Bonus question: Find a formula for the number of agents needed for n bits and t hours).
B. Suppose we want to send enough agents to be able to repeat the same task a second time with the remaining agents (i.e., those who did not die during the first invocation). How many agents are needed in that scenario?
Bonus question: Part A would require the same number of agents even if we increased the number of bits in the question by no more than X. What is this X and what is the connection between it and a recent event in IBM's history?
Different agents can access the same memory bit at the same time.
|
my guess is you need log_2(100000) which is 16.6, so you need 17 agents. This stems from each agent effectively enabling you to sort out half of all remaining bits.
To do this a second time, well best case none of the initial ones died, so you still need only 17, but worst case they all died, so you'd need 34 to be safe.
X would be 31072. no clue what IBM has to do with that number though.^^
/edit: yay solving this riddle enabled me to procrastinate learning for my exam tomorrow long enough for my video download to finish, so i can procrastinate another 45 minutes :D thanks! xD
/secondedit: and i completely ignored the time constraints, sorry.. nvm this post i guess -.-
|
|
|
United Kingdom3685 Posts
On March 30 2011 00:47 MisterD wrote: my guess is you need log_2(100000) which is 16.6, so you need 17 agents. This stems from each agent effectively enabling you to sort out half of all remaining bits.
To do this a second time, well best case none of the initial ones died, so you still need only 17, but worst case they all died, so you'd need 34 to be safe.
X would be 31072. no clue what IBM has to do with that number though.^^
/edit: yay solving this riddle enabled me to procrastinate learning for my exam tomorrow long enough for my video download to finish, so i can procrastinate another 45 minutes :D thanks! xD
/secondedit: and i completely ignored the time constraints, sorry.. nvm this post i guess -.-
That would only work if you had an infinite amount of time. You only have 2 hours and an agent takes 1 hour to run a query, so you only have enough time for 2 iterations, so the binary search won't work.
You definetely don't need 34 to be safe (assuming 17 was the correct number to begin with). That would make the riddle pointlessly trivial. Basically, you are guaranteed that not all agents will die from the search. You need to figure out how many are guaranteed to live.
How did you get 31072?
|
And also it's not guaranteed that each agent will go to a different bit, they could all take the same path (theoretically) That's what's messing me up.
|
My approach: + Show Spoiler +Arrange bits in a table of dimensions sqrt(100000) x sqrt(100000). Have an agent work on each line and on each column, that's 2*sqrt(100000) ~ 632 agents. The two agents which do not return OK will yield the coordinates of the faulty bit. The result is calculated in one hour, the second hour isn't even needed. If you want to be very exact, 100000 doesn't have an integer as its square root, so the table doesn't cover all bits or contains some blanks. In the unlikely case that the faulty bit is among those few leftovers, use the second hour to run agents on the remaining few bits to find the solution. Probably not an optimal solution, but not too bad for a quick naive approach.
Edit: decreased number of agents, but 2 hours required: + Show Spoiler +Again, separate the bits into sqrt(100000) groups with an agent working on each subset. After one hour, you know that the bit is among one of the groups of sqrt(100000) bits. In the second hour, use the method in the first spoiler to find the faulty bit in this smaller subset. Agents used: sqrt(100000) for the first hour plus 2*(sqrt(sqrt(100000)) for the second hour. That's ~352 agents.
Yet another edit: I don't know why I didn't think of this before. I used 2 dimensions for my approach. Of course you can use any number of dimensions. The question is what's the optimal number of dimensions for a given number of bits. I don't want to try to solve that question now though.
|
you still only need 17...no "queries" are even needed. All the agents have to do is run to their own subset and write down if each bit is a 0 or 1. Then they all meet up at the crew quarters(they can all go at once simultaneously) create the syndrome bits and compare.
|
On March 30 2011 00:56 Sayle wrote:Show nested quote +On March 30 2011 00:47 MisterD wrote: my guess is you need log_2(100000) which is 16.6, so you need 17 agents. This stems from each agent effectively enabling you to sort out half of all remaining bits.
To do this a second time, well best case none of the initial ones died, so you still need only 17, but worst case they all died, so you'd need 34 to be safe.
X would be 31072. no clue what IBM has to do with that number though.^^
/edit: yay solving this riddle enabled me to procrastinate learning for my exam tomorrow long enough for my video download to finish, so i can procrastinate another 45 minutes :D thanks! xD
/secondedit: and i completely ignored the time constraints, sorry.. nvm this post i guess -.- That would only work if you had an infinite amount of time. You only have 2 hours and an agent takes 1 hour to run a query, so you only have enough time for 2 iterations, so the binary search won't work. You definetely don't need 34 to be safe (assuming 17 was the correct number to begin with). That would make the riddle pointlessly trivial. Basically, you are guaranteed that not all agents will die from the search. You need to figure out how many are guaranteed to live. How did you get 31072?
2^17 - 100000 = 131072 - 100000 = 31072
and yeah if you don't run a complete binary search but use more agents so you can do the whole task in 2 hours, some will be guaranteed to stay alive. But if you do a full binary search, well you don't meet the time constraint, but in worst case, you'd kill your agent on every half you test, down till the last two bits where you let him test the wrong one and even that one dies. In that case, you really would need the double amount.
also the guy above me is right: you can let all agents start at once, the first checks half the grid, the second checks the first and third quarter, the third checks every uneven eigth part of all the bits, and in the end you can determine the faulty bit depending on which agent is still alive after one hour.
however, having two hours time, you could try to find a way to use up less agents by using those that survived a second time. That could enable you to need less agents.
|
United Kingdom3685 Posts
@Scorch: Yes, that method is a quick solution but not optimal. The bonus question pretty much shows that that's not the 'right' answer since in that method, any increase in the number of bits (beyond some tiny fraction due to non-integer roots) would require more agents.
|
If the thing was a square, or a cube this is what I would do, if it was a square all you need to do is send everyone in a line on both sides note down the ones missing and you have your coordinates for a 100.000 unit square you would need 317 or so if it was cubical you would only need 94. Silly me I was imagining a pirateship storage and a James Bond agent... I'm still 8 years old it seems.
|
On March 30 2011 01:04 Scorch wrote:My approach: + Show Spoiler +Arrange bits in a table of dimensions sqrt(100000) x sqrt(100000). Have an agent work on each line and on each column, that's 2*sqrt(100000) ~ 632 agents. The two agents which do not return OK will yield the coordinates of the faulty bit. The result is calculated in one hour, the second hour isn't even needed. If you want to be very exact, 100000 doesn't have an integer as its square root, so the table doesn't cover all bits or contains some blanks. In the unlikely case that the faulty bit is among those few leftovers, use the second hour to run agents on the remaining few bits to find the solution. Probably not an optimal solution, but not too bad for a quick naive approach.
to use the 2nd hour efficiently, you can just evolve this process, by giving every agent 18 lines (thats about the 4th root of 100000) or 18 columns in the 1st hour. Leaves you with an 18x18 block, where the faulty block is. Now repeat the game in 2nd hour again with your approach.
Brings us down to 36+2 = 38 Agents. (plus 2 because 2 die in the first hour) General solution by this aproach would be for x bits in h hours.
n = x ^ -(2^h) + 2(h-1) (rounded up)
|
...No one looked at the link I posted.... The first guy checks every other bit the second guy checks every other 2 bits then 2 bits the third guy checks every other 3 bits then 3 bits etc... When they meet back in the control room they each calculate whether the number of ones they encountered is odd or even. This creates the syndrome bit which they then can compare to the original syndrome bit that was calculated on earth before they left. The OR operation on the two syndrome bits gives the position of the faulty bit.
|
United Kingdom3685 Posts
Why would the bonus question ask what the formula was in terms of both bits and hours then. If your solution is correct, dominator, then the number of hours is irrelevant.
|
Indeed they are :p the total number of hours with my solution would be 1 or however long it takes for the agents to make a single pass like this. My guess is that the creator of the puzzle wasn't very familiar with computer architecture.
|
United Kingdom3685 Posts
|
I don't get it. Can't you just let one agent search a subset of 100000 bits and wait one hour to get the result?
|
no he will just die, and all you will know is that one of those 100000 bits is bad, which we already know. The agent will only tell you if the bad bit is in the subset he is searching(by dying or not), but not where in that subset.
|
What makes you say that?
And yes that is where I got it from, I'm going to try and keep up with these monthly quizzes, they seem fun.
|
I think the hamming code link the_dominator posted is the fastest in general (or maybe variations of it). With that method it would take 17 agents in one hour. I'm not sure how to use the two hours though.
This is definitely not the intended way but it's another method to do it with fairly few agents.
Let us label the bits 1-100,000. Send one agent to labels 0 mod 2, One agent to 0 mod 3, another to 1 mod 3, etc.
mod 2 uses 1 mod 3 uses 2 mod 5 uses 4 mod 7 uses 6 mod 11 uses 10 mod 13 uses 12.
In the first set, we use 35 agents to get (using the chinese remainder theorem) the unique mod of the error bit mod 30,300 (which is 2x3x5x7x11x13). Then in the second hour we need at most 3 more agents to get the error bit.
This is not as good as the hamming code though. The "price" of dividing 100,000 by p is p-1 agents while the price of dividing by two is only one agent in the other method.
|
On March 30 2011 01:04 Scorch wrote:My approach: + Show Spoiler +Arrange bits in a table of dimensions sqrt(100000) x sqrt(100000). Have an agent work on each line and on each column, that's 2*sqrt(100000) ~ 632 agents. The two agents which do not return OK will yield the coordinates of the faulty bit. The result is calculated in one hour, the second hour isn't even needed. If you want to be very exact, 100000 doesn't have an integer as its square root, so the table doesn't cover all bits or contains some blanks. In the unlikely case that the faulty bit is among those few leftovers, use the second hour to run agents on the remaining few bits to find the solution. Probably not an optimal solution, but not too bad for a quick naive approach. Edit: decreased number of agents, but 2 hours required: + Show Spoiler +Again, separate the bits into sqrt(100000) groups with an agent working on each subset. After one hour, you know that the bit is among one of the groups of sqrt(100000) bits. In the second hour, use the method in the first spoiler to find the faulty bit in this smaller subset. Agents used: sqrt(100000) for the first hour plus 2*(sqrt(sqrt(100000)) for the second hour. That's ~352 agents. Yet another edit: I don't know why I didn't think of this before. I used 2 dimensions for my approach. Of course you can use any number of dimensions. The question is what's the optimal number of dimensions for a given number of bits. I don't want to try to solve that question now though. I think yours is the best solution.
Additionally, I think the best number of dimensions would be 5 given this yields a whole number of agents; with 5 dimensions, 50 agents will be needed and the 5 who die will be the ones that will determine the location of the faulty bit.
Edit: Doh! How could I forget the Hamming Code? I love how TL nails quizzes like these with the first post. XD
|
On March 30 2011 01:43 TheAura wrote: no he will just die, and all you will know is that one of those 100000 bits is bad, which we already know. The agent will only tell you if the bad bit is in the subset he is searching(by dying or not), but not where in that subset.
Ah, OK. So you let run 2 simultaneously, each taking half of the subset in which the previous agent died.
Note: I didn't read the thread yet, on purpose, since I didn't want to spoil myself!
Well then, I'd say you need at least 50.000 agents, since you need to somehow narrow down the possible locations of the faulty bit plus then "go deeper" to find the actual bit. But since a query takes one hours and you only have two hours, you can only reduce the size of the subset once, which makes it necessary to have 50.000 agents each check 2 bits each, and then let another agent check one of the leftover bits.
That should be the answer to question a). As for the general formula: The available number of hours basically tells you how many levels you can go down. ! hour = you stay on level one, three hours = you can go to level 3, and so forth.
You can derive this formula empirically: Starting with 100.000 bits, you can observe this: With 1 hours you need 100.000 agents each covering 1 bit, with 2 hours you need 50.000 agents each covering 2 bits, with 3 hours you need 25.000 each covering 4 bit, with 4 hours you need 12.500 each covering 8 bit, and so forth. The formula for this is easily derived: A(t) = 100.000/(2^(n-1)). Looking at it the adjustment should be trivial (although I'm not sure):
The general formula is A(n,t) = n/(2^(n-1))
The answer to question b) You'd need 50.002, since in the worst case two agents will die during the first search.
edit, since I read the post above me: Obviously this assumes that you can't just change the order of how the information is stored.
|
@heishe the matrix solutions don't require changing the "order of information storage", it's just a way of visualizing the labeling.
|
On March 30 2011 02:06 blankspace wrote: @heishe the matrix solutions don't require changing the "order of information storage", it's just a way of visualizing the labeling.
Oh yeah, of course. Sorry then, ignore that comment and ignore my solution
|
United Kingdom3685 Posts
On March 30 2011 01:43 TadH wrote:What makes you say that? And yes that is where I got it from, I'm going to try and keep up with these monthly quizzes, they seem fun.
It was sarcasm...
|
On March 30 2011 01:05 THE_DOMINATOR wrote: you still only need 17...no "queries" are even needed. All the agents have to do is run to their own subset and write down if each bit is a 0 or 1. Then they all meet up at the crew quarters(they can all go at once simultaneously) create the syndrome bits and compare.
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.
|
okay so the info an agent can give 1) dying in the first search 2) dying in the second search 3) not dying
so it's simple trinary? we can represent the resulting string as n digits of [1-3] and we'd like to find the lowest n such that 3^n >=100000
therefore n = 11
the solution in terms of hours and n is (t+1)^agents>=n
O-o
edit: so i guess i should probably write up the actual process as well
i will be imprecise with the last digit just for ease of sake/reading. it should be like +1 on most of them
agent1 : search 0-33333 then search 33333-66666 agent2 : search 0-11111 + 33333-44444 + 66666-77777 then 11111-22222+44444-55555 + 77777-88888 and so on
so at the end let's say bot 1 dies in first search, bot 2 doesn't die, etc etc so we have a final string of 12312311121 (11 digits) that can uniquely identify up to something like 177,000 bits which is >=100000
edit@below yeah 11, sorry 13 was for 1 million, oops
|
On March 30 2011 03:40 JeeJee wrote: okay so the info an agent can give 1) dying in the first search 2) dying in the second search 3) not dying
so it's simple trinary? we can represent the resulting string as n digits of [1-3], and we'd like to find the lowest n such that 3^n >=100,000
therefore n = 13
the solution in terms of hours and n is (t+1)^agents>=n
O-o Yeah, but that's the easy bit. the second part is more interesting (and 3^11 > 100,000 btw, so it's 11).
|
On March 30 2011 01:04 Scorch wrote:My approach: + Show Spoiler +Arrange bits in a table of dimensions sqrt(100000) x sqrt(100000). Have an agent work on each line and on each column, that's 2*sqrt(100000) ~ 632 agents. The two agents which do not return OK will yield the coordinates of the faulty bit. The result is calculated in one hour, the second hour isn't even needed. If you want to be very exact, 100000 doesn't have an integer as its square root, so the table doesn't cover all bits or contains some blanks. In the unlikely case that the faulty bit is among those few leftovers, use the second hour to run agents on the remaining few bits to find the solution. Probably not an optimal solution, but not too bad for a quick naive approach. Edit: decreased number of agents, but 2 hours required: + Show Spoiler +Again, separate the bits into sqrt(100000) groups with an agent working on each subset. After one hour, you know that the bit is among one of the groups of sqrt(100000) bits. In the second hour, use the method in the first spoiler to find the faulty bit in this smaller subset. Agents used: sqrt(100000) for the first hour plus 2*(sqrt(sqrt(100000)) for the second hour. That's ~352 agents. Yet another edit: I don't know why I didn't think of this before. I used 2 dimensions for my approach. Of course you can use any number of dimensions. The question is what's the optimal number of dimensions for a given number of bits. I don't want to try to solve that question now though.
thats VERY interesting. continuing from your 2nd spoiler, i wanted to know if there is a sweet spot in terms of how many dimensions one would need
http://www.wolframalpha.com/input/?i=plot f(x,y) = (10^5)^(1/y)+ y*(((10^5)^(1/y))^(1/y))^(y-1) y from 1 to 5
http://www.wolframalpha.com/input/?i=plot f(x,y) = (10^5)^(1/y)+ y*(((10^5)^(1/y))^(1/y))^(y-1) y from 2.5 to 5
Seems to be that 4 is the dimension requiring the least amount of agents (should be 157). I will try to plot this in 3d with the number of bits as the 2nd variable and edit it in shortly.
/edit: aww crap ... somehow the Y shows up as factor ... i'll start over.
/edit: one dimension with 10^5 elements:
http://www.wolframalpha.com/input/?i=plot f(y) = (10^5)^(1/y)+ y*(((10^5)^(1/y))^(1/y))^(y-1) with y from 2 to 50 minimum is @ 11 dimensions with 31 agents http://www.wolframalpha.com/input/?i=plot f(y) = (10^5)^(1/y)+ y*(((10^5)^(1/y))^(1/y))^(y-1) with y from 6 to 15
3d plot with variable bits: http://www.wolframalpha.com/input/?i=3d plot f(x,y) = (y)^(1/x)+ x*(((y)^(1/x))^(1/x))^(x-1) with x from 6 to 50 and y from 10^3 to 10^8 interesting to see that the number of dimensions remains rather constant for 10^3 to 10^8 bits.
|
|
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
---
I will also add that X = 162,143.
|
I think the solution for part B is 13, but I'm not quite sure.
|
This seems kind of complicated.
The way I would approach it is first consider 1 hour have k agents each check n bits, and each bit needs to be checked m times.
constraints:
k >= m. kCm >= 100000 k*n = m*100000
So taking base case k = 2m.
I get that n = 500000
the smallest k that works is 20.
So in 1 hour you need 20 agents, but in 2hours I guess you could have same agent do twice the checks, so you would only need 10 agents.
So my answer is 10.
edit:
So the way this works is you divide the set of all bits into k sets. For any m of those k sets the intersection can not be more than 1 bit.
So once you have the 100000 bits, you run the 20 agents (in 2 hours you can just run 10 agents and then the same 10 agents again.) Out of the 20 results 10 will come out positive. So you have 10 sets that all intersect at just 1 bit, that's the bit that's broken.
Ok i reread the problem. If by agents dying you mean they permanently die, and can't be used during the second hour, then.you'll need a few extra.
First of all you really only need to run 19 agents total the last 1 could be gotten via elmination. If all ten agents die you know the right bit. If 1 lives you'll need 9more agents I guess...
So if agents die permanently you need 19 agents =(.
I haven't considered it from the start maybe there's a better way to sort through things.
edit 2:
OK OK OK OK.
You can have 20 checks total, but you really only need 8 intersections across each bit. This means that less agents will die in total, and we can decrease the amount of dead agents.
So once again by elimination we only need 19 checks. For the second hour we only need 9 live agents.
and the maximum that could have died in the first hour is 8 in this case, so that means that we only need 17 agents total.
17!
|
On March 30 2011 03:40 JeeJee wrote:okay so the info an agent can give 1) dying in the first search 2) dying in the second search 3) not dying so it's simple trinary? we can represent the resulting string as n digits of [1-3] and we'd like to find the lowest n such that 3^n >=100000 therefore n = 11 the solution in terms of hours and n is (t+1)^agents>=n O-o edit: so i guess i should probably write up the actual process as well i will be imprecise with the last digit just for ease of sake/reading. it should be like +1 on most of them agent1 : search 0-33333 then search 33333-66666 agent2 : search 0-11111 + 33333-44444 + 66666-77777 then 11111-22222+44444-55555 + 77777-88888 and so on so at the end let's say bot 1 dies in first search, bot 2 doesn't die, etc etc so we have a final string of 12312311121 (11 digits) that can uniquely identify up to something like 177,000 bits which is >=100000 edit@below yeah 11, sorry 13 was for 1 million, oops
This seems like it should work, and it does in fact give a better answer than my version.
I'll try to see if there's something more efficient, but there's likely to not be. Well done!
edit:
On the other hand in yours it's possible that all 11 bits die, so you would need 22 bits to guarantee a second check, 33 for the third, 44 for the fourth and etc. but in my solution only a maximum of 8 bits die so mine goes 17-25-33-41!!
|
On March 30 2011 04:26 Kiarip wrote: This seems kind of complicated.
The way I would approach it is first consider 1 hour have k agents each check n bits, and each bit needs to be checked m times.
constraints:
k >= m. kCm >= 100000 k*n = m*100000
So taking base case k = 2m.
I get that n = 500000
the smallest k that works is 20.
So in 1 hour you need 20 agents, but in 2hours I guess you could have same agent do twice the checks, so you would only need 10 agents.
So my answer is 10.
edit:
So the way this works is you divide the set of all bits into k sets. For any m of those k sets the intersection can not be more than 1 bit.
So once you have the 100000 bits, you run the 20 agents (in 2 hours you can just run 10 agents and then the same 10 agents again.) Out of the 20 results 10 will come out positive. So you have 10 sets that all intersect at just 1 bit, that's the bit that's broken.
Ok i reread the problem. If by agents dying you mean they permanently die, and can't be used during the second hour, then.you'll need a few extra.
First of all you really only need to run 19 agents total the last 1 could be gotten via elmination. If all ten agents die you know the right bit. If 1 lives you'll need 9more agents I guess...
So if agents die permanently you need 19 agents =(.
I haven't considered it from the start maybe there's a better way to sort through things.
edit 2:
OK OK OK OK.
You can have 20 checks total, but you really only need 8 intersections across each bit. This means that less agents will die in total, and we can decrease the amount of dead agents.
So once again by elimination we only need 19 checks. For the second hour we only need 9 live agents.
and the maximum that could have died in the first hour is 8 in this case, so that means that we only need 17 agents total.
17!
I think you're probably the closest, I'm going to post the answer in a spoiler when it's released by IBM.
|
OK, for two checks, I have mathematical proof that 18 are enough to have 11 which can ensure the second check.
This number feels WAY too big for me. My intuition says much better can be done here.
edit: + Show Spoiler [proof] +Each group of 3 agents can:
1st can check a first 7th, 2nd can check the second 7th, 3rd can check the third 7th in the first hour. 1st can check the fourth 7th, 2nd can check the fifth 7th, and 3rd can check the sixth 7th in the second hour
Therefor, each 3 agents can narrow it down to 1/7th of the possibilities, and since no two check the same, maximum of one out of the three will die.
7^6 = 117649 > 100000
Therefor, it takes 6 trios to systematically cover 100000 bits, and at worst, they will remain 6 pairs, greater than the 11 necessary to do a second check.
|
On March 30 2011 05:25 TadH wrote:Show nested quote +On March 30 2011 04:26 Kiarip wrote: This seems kind of complicated.
The way I would approach it is first consider 1 hour have k agents each check n bits, and each bit needs to be checked m times.
constraints:
k >= m. kCm >= 100000 k*n = m*100000
So taking base case k = 2m.
I get that n = 500000
the smallest k that works is 20.
So in 1 hour you need 20 agents, but in 2hours I guess you could have same agent do twice the checks, so you would only need 10 agents.
So my answer is 10.
edit:
So the way this works is you divide the set of all bits into k sets. For any m of those k sets the intersection can not be more than 1 bit.
So once you have the 100000 bits, you run the 20 agents (in 2 hours you can just run 10 agents and then the same 10 agents again.) Out of the 20 results 10 will come out positive. So you have 10 sets that all intersect at just 1 bit, that's the bit that's broken.
Ok i reread the problem. If by agents dying you mean they permanently die, and can't be used during the second hour, then.you'll need a few extra.
First of all you really only need to run 19 agents total the last 1 could be gotten via elmination. If all ten agents die you know the right bit. If 1 lives you'll need 9more agents I guess...
So if agents die permanently you need 19 agents =(.
I haven't considered it from the start maybe there's a better way to sort through things.
edit 2:
OK OK OK OK.
You can have 20 checks total, but you really only need 8 intersections across each bit. This means that less agents will die in total, and we can decrease the amount of dead agents.
So once again by elimination we only need 19 checks. For the second hour we only need 9 live agents.
and the maximum that could have died in the first hour is 8 in this case, so that means that we only need 17 agents total.
17!
I think you're probably the closest, I'm going to post the answer in a spoiler when it's released by IBM.
I'm pretty sure the other dude who got 11 by doing it base 3 has it right. There's no mistake in his work, you CAN do it with 11 agents.
EDIT:
For my solution I actually need a little bit less agents.
I only need to check 19 different regions (because the 20th can be assumed from process of elimination) and at most 8 are positive (and kill the agent.)
If you have 10 agents and 8 die you don't need anymore.
If you have 10 and 7 die in the first hour you're gonna need to do 9 more checks, and you have 3 left so you need 16 not 17.
But actually 16 is too much, because if you run the first 16 altogether you get at least 8 left over (9 whenever you need to check any more regions.)
So... I actually only need like 13.
Check the first 13, then if 7 die, I still have 6 more to finish up the total of 19 regions.
So 13 is the answer I get with my method. And 5 of those survive every single time.
So with this solution you would need a total of 13 + 8 = 21 to run this program twice (this is part B or w.e)
The other solution is 11 with none of them living for certain.
Here you would need 22 to run this program twice for sure.
So the answer to part A and part B requires separate algorithms? I guess so.
edit 2:
From what I understand the final answers to this problem would be:
11
22
3^11 - 100000 = 77147
Which according to google the amount of money that Watson beat the other jeopardy contests with.
gg.
|
@Kiarip: look up for a better part B.
|
a) 11 b) 18 bonus) IBM's watson
seem reasonable. question b is surprisingly tricky, but you're right that 18 does feel a little high. i'll see if i can do better
|
got it down to 17 just now.
edit: not sure my way is mathematically sound. Still positive at 18.
|
On March 30 2011 05:25 TadH wrote: I think you're probably the closest, I'm going to post the answer in a spoiler when it's released by IBM.
When is this going to be posted?
|
bleh, i got nothing good for B. i suck at this
|
On March 30 2011 07:24 EsX_Raptor wrote:Show nested quote +On March 30 2011 05:25 TadH wrote: I think you're probably the closest, I'm going to post the answer in a spoiler when it's released by IBM.
When is this going to be posted?
They post the answer on the ibm website on april 1st i believe
in any case ill update it here.
|
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
|
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
|
On March 30 2011 03:39 Kazius wrote:Show nested quote +On March 30 2011 01:05 THE_DOMINATOR wrote: you still only need 17...no "queries" are even needed. All the agents have to do is run to their own subset and write down if each bit is a 0 or 1. Then they all meet up at the crew quarters(they can all go at once simultaneously) create the syndrome bits and compare. 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
|
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.
|
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.
|
|
|
|
|