|
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.
|
|
|
|
|
|
EPT![[image loading]](http://i54.tinypic.com/29wjn7b.png)
![[image loading]](http://i56.tinypic.com/20px5bp.png)
![[image loading]](http://i54.tinypic.com/2e0srop.png)
![[image loading]](http://i52.tinypic.com/2m2g7qo.png)
![[image loading]](http://i56.tinypic.com/2ekn1io.png)
![[image loading]](http://i52.tinypic.com/2n4sjs.png)
![[image loading]](http://i53.tinypic.com/2ywaex4.png)
![[image loading]](http://i55.tinypic.com/ll36g.png)
