Since you don't allow open source software on your PC, you will purchase 0 copies of a closed source game with a linux port. Hence users like you don't add an incentice to port a closed source game (which isn't a good or a bad thing to me).
Porting to linux opens up the market of those people who run linux but do not run windows, and who also don't have a philosophical objection to closed source software. Those users are so few that it simply isn't financially worthwhile (unless you are writting a portable game to start with and adding linux has a tiny incremental cost).
When you get to second grade maybe your teacher will let you look at the dictionary and you'll learn that an analogy is a comparison based upon similarity in some areas between things which are not similar overall.
Yes automobiles are dissimilar to DRM. That's why an analogy can be made between the parts that are in fact similar.
They don't have to give away the software, however, they can't stop someone from buying one copy and then giving away copies of it (assumming they don't have non-free components - in which case those components would need to be removed).
If you get your hands on a copy the GPL kicks in, but the GPL doesn't force them to pay for the bandwidth so you can have a free copy.
Babylon 5 used CGI heavily when Trek was using models. Of course Trek now uses CGI; perhaps that one was inevitable, but they probably adopted it sooner because of the example of Babylon 5.
I seriously doubt it. The cost of CGI had been dropping (and continues to do so) relative to using models. CGI was cheaper at that point then using models - for Babylon 5. For Trek CGI was still more expensive, because they already had the models.
If you were starting from scratch CGI was cheaper. If you had already built a bunch of models then models were cheaper. Trek exists solely to make money, as soon as doing CGI was cheap enough to make the change worthwhile they did it.
I guess you could argue that Babylon 5's use of CGI helped bring the price down faster.
If you don't secure your wireless network, then people can use it. If you don't want people using your wireless network then it's your problem to secure it.
I would assume that something like WEP would be good enough to satisfy the bill. Since, although it is a broken security system, you can't accidently stumble into it the way you can with an open wireless network. Heck set the WEP key to your company name and legitimate users (and real crackers) won't be inconvienced at all, but pdopld who happen to turn on their laptop in the park opposite won't accidently login.
Essentially the bill would provide an 'it was an accident/I thought it was public access' defense. If the person does something that can be shown to be malicious or would indicate they knew it wasn't public then the usual rules would apply.
Personally I think it's a great idea. It's one more encouragement for people to secure their damn networks.
As for printing I would expect if you printed a hundred page document you could claim it was an accident. Though sending some infinite looping postscript code would, I suspect, be judged intentional:)
In 2002 I received over 18,000 pieces of spam, for a total of 163 megabytes.
You get much smaller spams than me...
In 2002 my spam filter (which didn't come close to catching everything) caught 4546 spams for a total of 78 megabytes.
My spam has noticably increased this year with more of it getting past my filter (which I think I've fixed now). My spam folder for March has 854 spams in it, for 18 megabytes. Multiplying those number by 12 is too scary to even contemplate.
I use a seperate email address for things like online shopping and web site account creations and the like - it's a spam magnet, but I only check it when I'm actually expecting something (because I just ordered a book or something) so I don't care.
I do seem to get at least 2 copies of each spam since sholden@*.cs.usyd.edu.au ends up in my mailbox.
"If you don't beleive in evolution you don't beleive in conventional medicine and it would be unethical for you to make recommendations to patients based on something you beleived to be untrue."
I disagree with that statement on two counts.
People exist who do not believe in evolution and who do believe in conventional medicine. The two beliefs may be inconsistant and contradict each other, but people hold conflicting beliefs all the time. Our brains cope just fine believing things which contradict.
Secondly, I don't think it is unethical to make recommendations that I don't believe to be true. If those recommendations are the required or best practice of a role I have. I consider it the same as doing something that I don't believe is the correct action because a role I have requires it. If I was a soldier who thought that the US should not have invaded Iraq without a UN backed coalition, it wouldn't be unethical for me to do my job as a soldier in Iraq - I should follow orders even if I disagree with them (unless they are illegal).
Creationists tend not to deny the existance of what they call 'micro-evolution' (I think that's the name) which bacteria evolution counts as. That micro and macro evolution are actually exactly the bloody same doesn't matter.
Even if they do, then all that matters is whether they follow the required practiced (and hopefully best practice). If they don't then they'll get booted, not because of their beliefs but because of their actions.
Dismissing evolution is not the same a insisting on a flat Earth. The latter is obviously false through every day experiences, and even measureable by a 'normal' person - unless you have an exotic flat earth theory (where say light is affected by the Earth's gravity more than it should be and hence curves a lot creating the horizon effect, and I guess magical teleporters beam you from one end to the other). After all any one who can go to med school can travel around the world on transport ships...
Even so a flat earther could make a compotent doctor too...
Creationists have choosen to believe their religion over their science. I don't think that makes them morons in other areas. It just means they have choosen to believe the interpretation which is not favoured by evidence in order to not face a challenge to their belief system. People do that all the time. A pro-iraq-war person might state that war with Iraq has *nothing* to do with oil - they are clearly are letting their beliefs get in the way of their logic. An anti-iraq-war person might state that war with Iraq is *all* about all - they are doing the same. It doesn't make them bad doctors.
If they always do that they won't make a good scientist. Since the belief causes actions that conflict with performing the job of a scientist correctly.
However, they might make a good doctor. As long as they don't have beliefs such as "prayer should be used *instead* of surgery", their beliefs shouldn't affect their performance in their job.
People will always make illogical decisions in some areas, it does not necessarily mean they are incompotent.
Practicing medicine as a doctor doesn't involve much scientific work (depending on the type of doctor) anyway.
Do you really think a creationist will be inherintly worse at prescribing pills than an athiest? Or at interpreting xrays? Or at performing heart surgery?
Anyway a creationist who has actually thought about evolution and decided they think it is unlikely will quite possibly make a better scientist than someone who just believes everything they were told by their high school teacher who probably graduated in the bottom half of his/her high school...
Now I admit dismissing evolution is a pretty damn big conclusion to reach - but maybe they are actually thinking about it and are still forming their opinion, just at that very moment they are leaning towards creationism.
I don't qualify as 'traitorous', since the US isn't my country...
And no I don't pay much attention to the AG of some irrelevant little country on the other side of an ocean. Other than giggling at his pathetic attempts to create a modern police state.
If the student can afford the fees then the capitalistic university should accept them. The university doesn't make more profit from those who become practising doctors than from those who graduate and go to the beach.
A state funded university is different, since the state benefits from more doctors. But state funded education is socialism.
Doctors' beliefs DO guide their actions, just like anyone else.
Obviously, but the beliefs themselves don't matter to judging whether the doctor is compotent or not.
The actions determine that.
For example, it doesn't matter what reason the doctor had for prefering stats to a scalpel - what matters is the choice itself, not the reasoning (or lack thereof) behind it. .
If I qualify for the course and can pay the fees then why should I be denied a place in the course just because I personally think medicince is a load of crock?
Maybe I'll learn that it isn't? Maybe I'll prove it is once I have the required learning, and we can all go back to praying for the sick?
If I believe, say, blood transfusions are evil, and hence will not allow myself to have one, but don't mind others having them, why shouldn't I be a doctor?
If my belief means I refuse my patients blood transfusions, or fail to mention they are a possible treatment for some condition, then I obviously shouldn't be a practising doctor. Not because of my beliefs, but because of the actions (or inactions) those beliefs result in. If another doctor did the same, because they were embaressed by their inability to pronouce 'transfusion' the results are identical and so should be the ban on practicing.
And what about those who want to study medicine but don't want to become doctors? I guess a socialist might ban them taking up a valuable slot - but a free market capitalist type couldn't do without being hypocritical. (We'll ignore those that study medicine in order to be scientists and never actually practice).
Well, I'm not going to go through the effort of proving it, but as I said log3(n) is probably a lower bound.
Since I already replied showing that the lower bound is higher than log3(n) then of course log3(n) is a lower bound. So is 1 after all.
If you consider that each weighing generates a balanced ternary digit then you can construct a number of weighings that give you the answer by looking up a table.
The requirement would be that each marble is assigned a number if that number is the result then that marble is heavier, if the resulting number is the negatin then that marble is lighter. Clearly this means the number 0 can't be used (since 0 == -0).
In order to do the weighings each weighing needs equal numbers of marbles on each side. That restricts us further. Essentially we create a table, for the case of n=12 we would construct:
A 0 0 1 #padding for idiotic filter which makes life hard B 0 1 -1 #padding for idiotic filter which makes life hard C 0 1 0 #padding for idiotic filter which makes life hard D 0 1 1 #padding for idiotic filter which makes life hard E 1 -1 -1 #padding for idiotic filter which makes life hard F 1 -1 0 #padding for idiotic filter which makes life hard G 1 -1 1 #padding for idiotic filter which makes life hard H 1 0 -1 #padding for idiotic filter which makes life hard I 1 0 0 #padding for idiotic filter which makes life hard J 1 0 1 #padding for idiotic filter which makes life hard K 1 1 -1 #padding for idiotic filter which makes life hard L 1 1 0 #padding for idiotic filter which makes life hard
Each column becomes a weighing of -1 marbles.vs. +1 marbles. That means we need an equal number of -1 and 1 digits in each column. To do this we can negate rows.
Column 1 needs 4 1 turned into -1s. Column 2 needs a 1 turned to a -1. And column 3 is fine.
Column 2 can be fixed by changing C from 0,1,0 to 0,-1,0. Column 1 can be fixed by flipping 101, 10-1, 110, and 1-10 - we simply make one column 0 and the other column we use both 1 and -1 - this not changing the other 2 columns.
So we have (sideways due to idiotic 'too few characters per line filter'):
A B C D E F G H I J K L 0 0 0 0 1 -1 1 -1 1 -1 1 -1 0 1 -1 1 -1 1 -1 0 0 0 1 -1 1 -1 0 1 -1 0 1 1 0 -1 -1 0
That gives us three weighings: FHJL.vs. EGIK CEGL.vs. BDFK BEJK.vs. ADGH
The results give us a 3 digit balanced ternary number which we look up in the table. If it is there then that marble is heavier. If it isn't we look up the negation, that marble is lighter.
So each marble is simply assigned a positive number (we then negate some of them to balance the weighings). We need an even number of non-0 digits in each column, this means we can't use '1 1 1' in the three digit case (so four 13 marbles we would need 4 weighings).
Essentially W weighings gives us 3^W numbers ranging from -(3^W-1)/2 to (3^W-1)/2. We only use the positive ones (negating some of them later) so we have 1 to (3^W-1)/2, We can't (3^W-1)/2 itself since it results in an off number of 1s in each column. So we have 1 to (3^W-1)/2-1.
That means W weighings can be used to determine which marble is odd in a set of (3^W-1)/2-1 marbles. That's the opposite of how we want it expressed - since we will know the marble count and want to know W. So do some simple math:
N = (3^W-1)/2-1 N+1 = (3^W-1)/2 2N+2 = 3^W-1 2N+3 = 3^W log3(2N+3) = W
Hence:
W = log3(2N+3)
Which is what I put in my first post on this topic...
That's a better lower bound than the log3(2N+2) one in my previous reply to you.
log3(2N+3) is the minimum weighings for N marbles if the weighings are done with no branching. In other words the results of previous weighings do not effect which marbles to weigh next.
Hence with 1 weighing you have 3 outcomes. With 2 you have 9 outcomes. With 3 you have 27 outcomes. With W you have 3^W outcomes.
If there are N balls, then there are 2N possible answers. Obviously you need at least as many outcomes as possible answers.
Hence 3^W = 2N Simple math: W = log3(2N)
We can easily show log3(2N+1) - since the result: [even, even, even] can never tell if the odd ball is heavier or lighter, since we obviously never weighed it:)
With more math we might be able to raise it a little more...
Damn you Americans and your cheap bandwidth. 1.5Mb/256kb at cheaper then my 512kb/128kb and I bet you aren't charged 13.9c a MB past 4500MB (of course 13.9 of our cents are 8.34 or so of yours).
I added the big-O notation where I shouldn't have since in this problem the answer of 3 is *so* much better than 4:)
The post I replied to didn't use big-O and I suspect the author's solution was the standard first attempt (which ignores the usefulness of the tri-value output of the scales)...
I already posted code for the best solution I know of which does it in 3. Another **SPOILER** below...
However, back in high school when I first came across this problem a few of us came up with a solution by making sure that every weighing counted. A weighing has three outcomes so in three weighings you have a tree with 27 leaf nodes - since there are only 24 possible outcomes we managed to only have 1 unused leaf in each of the three main branches it'd work.
We solved it with a decision tree, I'll try and recall the reasoning we used (I use the terms high and low to mean weights which are possibilities for the bad marble and must be heavier or lighter, and normal for known good marbles):
First weigh is 4.vs. 4. If it is equal then the solution is easy. You just weigh any three of those 8 against 3 of the remaining four. It leaves you with either 3 all high or 3 all low, or 1 competely unknown which must be the bad marble. Those three are easy to do in one weighing.
If the first weighing is uneven, then you now have three sets: 4 high, 4 low, and 4 normal.
To succeed in one weighing we need to reduce the possibilties to just 3 marbles. Since we know if they are low or high, one weighing will give us the answer from there.
If the second weighing reads even then the unweighed marbles must contain the bad marble, this means we can only leave 3 non-normal marbles out of the weighing. So we must weigh at least 5 of the non-normal marbles on the second weighing.
An uneven reading must also only produce three possible bad marbles. That means only three of one type (low or high) on one side. And marbles of the opposite type on the opposite side count. We only have 4 normals available which restricts us.
So we simple enumerate the possible weighings and see if anything works:
left right out NNNNH HHLLL HL bad (1H and 3Ls opposite) NNNNH HHHLL LL is one possible weighing It gives: NNNNH = HHHLL (LL) => NNNNN = NNNNN (LL)-solvable NNNNH < HHHLL (LL) => NNNNN < HHHNN (NN)-solvable NNNNH > HHHLL (LL) => NNNNH > NNNLL (NN)-solvable
So there we go an answer!
Giving us the following algorithm: (sorry about the annoying extra words, the stupid slashdot software didn't like my short lines...)
1?2?3?4?.vs. 5?6?7?8? # i need more characters per line - = : 1N2N3N.vs. 9?A?B? # i need more characters per line -- = : 1N.vs. C? # i need more characters per line --- = impossible # i need more characters per line --- > C light # i need more characters per line --- < C heavy # i need more characters per line -- > : 9H.vs. AH # i need more characters per line --- = B light # i need more characters per line --- > A light # i need more characters per line --- < 9 light # i need more characters per line -- < : 9H.vs. AH # i need more characters per line --- = B heavy # i need more characters per line --- > 9 heavy # i need more characters per line --- < A heavy # i need more characters per line - > : 9NANBNCN1H.vs. 2H3H4H5L6L # i need more characters per line -- = : 7L.vs. 8L # i need more characters per line --- = impossible # i need more characters per line --- > 8 light # i need more characters per line --- < 7 light # i need more characters per line -- > 5L.vs. 6L # i need more characters per line --- = 1 heavy # i need more characters per line --- > 6 light # i need more characters per line --- < 5 light # i need more characters per line -- < 2H.vs. 3H # i need more characters per line --- = 4 heavy --- > 2 heavy --- < 3 heavy - < : NANBNCN5H.vs. 6H7H8H1L2L -- = : 3L.vs. 4L --- = impossible --- > 4 light ---
Slashdot Mirror
Double the price isn't 'horrendously' expensive...
There are these things called batteries. Of course the article mentions them, but who reads the articles anyway...
RAM only needs a trickle to keep refreshed...
Since you don't allow open source software on your PC, you will purchase 0 copies of a closed source game with a linux port. Hence users like you don't add an incentice to port a closed source game (which isn't a good or a bad thing to me).
Porting to linux opens up the market of those people who run linux but do not run windows, and who also don't have a philosophical objection to closed source software. Those users are so few that it simply isn't financially worthwhile (unless you are writting a portable game to start with and adding linux has a tiny incremental cost).
When you get to second grade maybe your teacher will let you look at the dictionary and you'll learn that an analogy is a comparison based upon similarity in some areas between things which are not similar overall.
Yes automobiles are dissimilar to DRM. That's why an analogy can be made between the parts that are in fact similar.
Maybe you should learn how to read legalese.
They don't have to give away the software, however, they can't stop someone from buying one copy and then giving away copies of it (assumming they don't have non-free components - in which case those components would need to be removed).
If you get your hands on a copy the GPL kicks in, but the GPL doesn't force them to pay for the bandwidth so you can have a free copy.
I seriously doubt it. The cost of CGI had been dropping (and continues to do so) relative to using models. CGI was cheaper at that point then using models - for Babylon 5. For Trek CGI was still more expensive, because they already had the models.
If you were starting from scratch CGI was cheaper. If you had already built a bunch of models then models were cheaper. Trek exists solely to make money, as soon as doing CGI was cheap enough to make the change worthwhile they did it.
I guess you could argue that Babylon 5's use of CGI helped bring the price down faster.
You don't distinguish.
:)
If you don't secure your wireless network, then people can use it. If you don't want people using your wireless network then it's your problem to secure it.
I would assume that something like WEP would be good enough to satisfy the bill. Since, although it is a broken security system, you can't accidently stumble into it the way you can with an open wireless network. Heck set the WEP key to your company name and legitimate users (and real crackers) won't be inconvienced at all, but pdopld who happen to turn on their laptop in the park opposite won't accidently login.
Essentially the bill would provide an 'it was an accident/I thought it was public access' defense. If the person does something that can be shown to be malicious or would indicate they knew it wasn't public then the usual rules would apply.
Personally I think it's a great idea. It's one more encouragement for people to secure their damn networks.
As for printing I would expect if you printed a hundred page document you could claim it was an accident. Though sending some infinite looping postscript code would, I suspect, be judged intentional
In 2002 my spam filter (which didn't come close to catching everything) caught 4546 spams for a total of 78 megabytes.
My spam has noticably increased this year with more of it getting past my filter (which I think I've fixed now). My spam folder for March has 854 spams in it, for 18 megabytes. Multiplying those number by 12 is too scary to even contemplate.
I use a seperate email address for things like online shopping and web site account creations and the like - it's a spam magnet, but I only check it when I'm actually expecting something (because I just ordered a book or something) so I don't care.
I do seem to get at least 2 copies of each spam since sholden@*.cs.usyd.edu.au ends up in my mailbox.
People exist who do not believe in evolution and who do believe in conventional medicine. The two beliefs may be inconsistant and contradict each other, but people hold conflicting beliefs all the time. Our brains cope just fine believing things which contradict.
Secondly, I don't think it is unethical to make recommendations that I don't believe to be true. If those recommendations are the required or best practice of a role I have. I consider it the same as doing something that I don't believe is the correct action because a role I have requires it. If I was a soldier who thought that the US should not have invaded Iraq without a UN backed coalition, it wouldn't be unethical for me to do my job as a soldier in Iraq - I should follow orders even if I disagree with them (unless they are illegal).
Creationists tend not to deny the existance of what they call 'micro-evolution' (I think that's the name) which bacteria evolution counts as. That micro and macro evolution are actually exactly the bloody same doesn't matter.
Even if they do, then all that matters is whether they follow the required practiced (and hopefully best practice). If they don't then they'll get booted, not because of their beliefs but because of their actions.
Dismissing evolution is not the same a insisting on a flat Earth. The latter is obviously false through every day experiences, and even measureable by a 'normal' person - unless you have an exotic flat earth theory (where say light is affected by the Earth's gravity more than it should be and hence curves a lot creating the horizon effect, and I guess magical teleporters beam you from one end to the other). After all any one who can go to med school can travel around the world on transport ships...
Even so a flat earther could make a compotent doctor too...
Creationists have choosen to believe their religion over their science. I don't think that makes them morons in other areas. It just means they have choosen to believe the interpretation which is not favoured by evidence in order to not face a challenge to their belief system. People do that all the time. A pro-iraq-war person might state that war with Iraq has *nothing* to do with oil - they are clearly are letting their beliefs get in the way of their logic. An anti-iraq-war person might state that war with Iraq is *all* about all - they are doing the same. It doesn't make them bad doctors.
If they always do that they won't make a good scientist. Since the belief causes actions that conflict with performing the job of a scientist correctly.
However, they might make a good doctor. As long as they don't have beliefs such as "prayer should be used *instead* of surgery", their beliefs shouldn't affect their performance in their job.
I don't think so.
People will always make illogical decisions in some areas, it does not necessarily mean they are incompotent.
Practicing medicine as a doctor doesn't involve much scientific work (depending on the type of doctor) anyway.
Do you really think a creationist will be inherintly worse at prescribing pills than an athiest? Or at interpreting xrays? Or at performing heart surgery?
Anyway a creationist who has actually thought about evolution and decided they think it is unlikely will quite possibly make a better scientist than someone who just believes everything they were told by their high school teacher who probably graduated in the bottom half of his/her high school...
Now I admit dismissing evolution is a pretty damn big conclusion to reach - but maybe they are actually thinking about it and are still forming their opinion, just at that very moment they are leaning towards creationism.
I don't qualify as 'traitorous', since the US isn't my country...
And no I don't pay much attention to the AG of some irrelevant little country on the other side of an ocean. Other than giggling at his pathetic attempts to create a modern police state.
So what?
Why shouldn't I be allowed to put excessive effort into something?
If the student can afford the fees then the capitalistic university should accept them. The university doesn't make more profit from those who become practising doctors than from those who graduate and go to the beach.
A state funded university is different, since the state benefits from more doctors. But state funded education is socialism.
The actions determine that.
For example, it doesn't matter what reason the doctor had for prefering stats to a scalpel - what matters is the choice itself, not the reasoning (or lack thereof) behind it.
.
Why should they?
If I qualify for the course and can pay the fees then why should I be denied a place in the course just because I personally think medicince is a load of crock?
Maybe I'll learn that it isn't? Maybe I'll prove it is once I have the required learning, and we can all go back to praying for the sick?
If I believe, say, blood transfusions are evil, and hence will not allow myself to have one, but don't mind others having them, why shouldn't I be a doctor?
If my belief means I refuse my patients blood transfusions, or fail to mention they are a possible treatment for some condition, then I obviously shouldn't be a practising doctor. Not because of my beliefs, but because of the actions (or inactions) those beliefs result in. If another doctor did the same, because they were embaressed by their inability to pronouce 'transfusion' the results are identical and so should be the ban on practicing.
And what about those who want to study medicine but don't want to become doctors? I guess a socialist might ban them taking up a valuable slot - but a free market capitalist type couldn't do without being hypocritical. (We'll ignore those that study medicine in order to be scientists and never actually practice).
Since I already replied showing that the lower bound is higher than log3(n) then of course log3(n) is a lower bound. So is 1 after all.
If you consider that each weighing generates a balanced ternary digit then you can construct a number of weighings that give you the answer by looking up a table.
The requirement would be that each marble is assigned a number if that number is the result then that marble is heavier, if the resulting number is the negatin then that marble is lighter. Clearly this means the number 0 can't be used (since 0 == -0).
In order to do the weighings each weighing needs equal numbers of marbles on each side. That restricts us further. Essentially we create a table, for the case of n=12 we would construct:
Each column becomes a weighing of -1 marbles .vs. +1 marbles. That means we need an equal number of -1 and 1 digits in each column. To do this we can negate rows.
.vs. EGIK .vs. BDFK .vs. ADGH
Column 1 needs 4 1 turned into -1s. Column 2 needs a 1 turned to a -1. And column 3 is fine.
Column 2 can be fixed by changing C from 0,1,0 to 0,-1,0. Column 1 can be fixed by flipping 101, 10-1, 110, and 1-10 - we simply make one column 0 and the other column we use both 1 and -1 - this not changing the other 2 columns.
So we have (sideways due to idiotic 'too few characters per line filter'):
A B C D E F G H I J K L
0 0 0 0 1 -1 1 -1 1 -1 1 -1
0 1 -1 1 -1 1 -1 0 0 0 1 -1
1 -1 0 1 -1 0 1 1 0 -1 -1 0
That gives us three weighings:
FHJL
CEGL
BEJK
The results give us a 3 digit balanced ternary number which we look up in the table. If it is there then that marble is heavier. If it isn't we look up the negation, that marble is lighter.
So each marble is simply assigned a positive number (we then negate some of them to balance the weighings). We need an even number of non-0 digits in each column, this means we can't use '1 1 1' in the three digit case (so four 13 marbles we would need 4 weighings).
Essentially W weighings gives us 3^W numbers ranging from -(3^W-1)/2 to (3^W-1)/2. We only use the positive ones (negating some of them later) so we have 1 to (3^W-1)/2, We can't (3^W-1)/2 itself since it results in an off number of 1s in each column. So we have 1 to (3^W-1)/2-1.
That means W weighings can be used to determine which marble is odd in a set of (3^W-1)/2-1 marbles. That's the opposite of how we want it expressed - since we will know the marble count and want to know W. So do some simple math:
N = (3^W-1)/2-1
N+1 = (3^W-1)/2
2N+2 = 3^W-1
2N+3 = 3^W
log3(2N+3) = W
Hence:
W = log3(2N+3)
Which is what I put in my first post on this topic...
That's a better lower bound than the log3(2N+2) one in my previous reply to you.
log3(2N+3) is the minimum weighings for N marbles if the weighings are done with no branching. In other words the results of previous weighings do not effect which marbles to weigh next.
For bra
ceiling(log3(12))+1 = ceiling(2.262)+1 = 3+1 = 4
So clearly you can do it better than that.
A log3 lowerbound is pretty simple...
:)
A weighing only has three outcomes.
Hence with 1 weighing you have 3 outcomes.
With 2 you have 9 outcomes.
With 3 you have 27 outcomes.
With W you have 3^W outcomes.
If there are N balls, then there are 2N possible answers. Obviously you need at least as many outcomes as possible answers.
Hence 3^W = 2N
Simple math: W = log3(2N)
We can easily show log3(2N+1) - since the result: [even, even, even] can never tell if the odd ball is heavier or lighter, since we obviously never weighed it
With more math we might be able to raise it a little more...
Damn you Americans and your cheap bandwidth. 1.5Mb/256kb at cheaper then my 512kb/128kb and I bet you aren't charged 13.9c a MB past 4500MB (of course 13.9 of our cents are 8.34 or so of yours).
Mine (internode - in Australia) supports it, in fact they even allow four concurrent ADSL logins for those who find NAT too complicated...
Why not find an ISP with a clue who allows multiple machines to use the connection. Mine does, but I'm in a different country so that's not much use.
If you are going to pay extra I'd want IPs not NAT...
True enough...
:)
I added the big-O notation where I shouldn't have since in this problem the answer of 3 is *so* much better than 4
The post I replied to didn't use big-O and I suspect the author's solution was the standard first attempt (which ignores the usefulness of the tri-value output of the scales)...
No you don't.
.vs. 4. If it is equal then the solution is easy. You just weigh any three of those 8 against 3 of the remaining four. It leaves you with either 3 all high or 3 all low, or 1 competely unknown which must be the bad marble. Those three are easy to do in one weighing.
.vs. 5?6?7?8? # i need more characters per line .vs. 9?A?B? # i need more characters per line .vs. C? # i need more characters per line .vs. AH # i need more characters per line .vs. AH # i need more characters per line .vs. 2H3H4H5L6L # i need more characters per line .vs. 8L # i need more characters per line .vs. 6L # i need more characters per line .vs. 3H # i need more characters per line .vs. 6H7H8H1L2L .vs. 4L
I already posted code for the best solution I know of which does it in 3. Another **SPOILER** below...
However, back in high school when I first came across this problem a few of us came up with a solution by making sure that every weighing counted. A weighing has three outcomes so in three weighings you have a tree with 27 leaf nodes - since there are only 24 possible outcomes we managed to only have 1 unused leaf in each of the three main branches it'd work.
We solved it with a decision tree, I'll try and recall the reasoning we used (I use the terms high and low to mean weights which are possibilities for the bad marble and must be heavier or lighter, and normal for known good marbles):
First weigh is 4
If the first weighing is uneven, then you now have three sets: 4 high, 4 low, and 4 normal.
To succeed in one weighing we need to reduce the possibilties to just 3 marbles. Since we know if they are low or high, one weighing will give us the answer from there.
If the second weighing reads even then the unweighed marbles must contain the bad marble, this means we can only leave 3 non-normal marbles out of the weighing. So we must weigh at least 5 of the non-normal marbles on the second weighing.
An uneven reading must also only produce three possible bad marbles. That means only three of one type (low or high) on one side. And marbles of the opposite type on the opposite side count. We only have 4 normals available which restricts us.
So we simple enumerate the possible weighings and see if anything works:
left right out
NNNNH HHLLL HL bad (1H and 3Ls opposite)
NNNNH HHHLL LL is one possible weighing
It gives:
NNNNH = HHHLL (LL) => NNNNN = NNNNN (LL)-solvable
NNNNH < HHHLL (LL) => NNNNN < HHHNN (NN)-solvable
NNNNH > HHHLL (LL) => NNNNH > NNNLL (NN)-solvable
So there we go an answer!
Giving us the following algorithm: (sorry about the annoying extra words, the stupid slashdot software didn't like my short lines...)
1?2?3?4?
- = : 1N2N3N
-- = : 1N
--- = impossible # i need more characters per line
--- > C light # i need more characters per line
--- < C heavy # i need more characters per line
-- > : 9H
--- = B light # i need more characters per line
--- > A light # i need more characters per line
--- < 9 light # i need more characters per line
-- < : 9H
--- = B heavy # i need more characters per line
--- > 9 heavy # i need more characters per line
--- < A heavy # i need more characters per line
- > : 9NANBNCN1H
-- = : 7L
--- = impossible # i need more characters per line
--- > 8 light # i need more characters per line
--- < 7 light # i need more characters per line
-- > 5L
--- = 1 heavy # i need more characters per line
--- > 6 light # i need more characters per line
--- < 5 light # i need more characters per line
-- < 2H
--- = 4 heavy
--- > 2 heavy
--- < 3 heavy
- < : NANBNCN5H
-- = : 3L
--- = impossible
--- > 4 light
---