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