>You are give 12 identical looking balls. One of them is fake (could be heavier or lighter) than the rest of the 11 (all the others weight exactly the same). You a provided with a simple mechanical balance. Find the fake ball(and whether it's heavier or lighter) in minimum weighings.
The solution to the above is essentially a binary search problem but then it should require 4 steps in the worst case.
What is the extra information we have that allows us to determine the fake ball in 3 steps?
Other urls found in this thread:
>do my homework please
>>>Cred Forums.org/rules#global2
You don't need extra information, just start by grouping the balls into three lots of four, then weigh any two. If they weigh the same, the ball is in the unweighed lot of four. Proceed as normal.
Easy.
You can't figure out which ball is in three steps in the worst case scenario with your method.
I know how the solution works. What I need to know is why it does because a binary search on a group of 12 would require at most 4 steps. Clearly the problem provides us with some information that allows us to cut it down to 3.
>12 balls
>not 12 dicks
Meh.
1. Divide into three groups of four, weight 2 groups
2. Divide the group of 4 with the outlier in half, weight the 2.
3. Divide the group of 2 with the outlier in half. Weight both balls.
There's three steps.
Soo, you want to get the fake ball, as well as figure out whether it's lighter or heavier in three steps?
Probably change the three group bit to the second or third step then, because you'll have a known quantity of non-fake balls to weigh against.
I said in the worst case scenario. If the first two groups don't weight the same, you have to make another measurement and you just lost 2 opportunities. You can't figure out which ball is the different one with only one more weighting.
No, because if they don't weight the same in the first step, you can swap 2 balls with each side in the second second to get to step three immediately.
>then it should require 4 steps in the worst case.
I think I'm too stupid, my solution requires 3 measurements
Divide in to two groups of 6, weigh
Take the group with the outlier and divide into three groups of 2, pick any two to weigh
If they weigh the same, weigh the balls you didn't pick
If they don't then chose the group with the outlier and weigh them.
I'm sorry, I don't follow. Let's say you have groups A, B and C. You weight A and B and A is lighter than B. What do you do now?
This does not work. If you weigh the two groups of six, which six are you going to weigh next? The heavier or the lighter?
You swap two of group A with two of group B to find out whether the fake ball is heavier or lighter than the real ones.
what? this doesn't help at all
Are you stupid?
You obviously stated that the fake could be lighter OR heavier.
Of course you need to determine which it actually is.
But that way you have to waste another measurement. And what if you pick four balls that weight the same?
Nah, you can actually determine that with even 4 real balls.
But how do you know if you moved a heavy one or light one.
Two of them then become the control group for the third measurement. Look, you need to setup an algorithm for this problem, it's clear you can't visualize it in your mind.
nice try, but even though I just did your homework, I'm not going to do your homework
The fact that you can make an assumption on some untested set of balls since you know there is one, and only one fake ball. Thus if you test 8 of your balls then if they come out balanced you have a reference weight, and you know one of the remaining 3 balls are fake.
>The solution to the above is essentially a binary search problem but then it should require 4 steps in the worst case.
Yeah, four steps if you don;t now the weight of the fake
>What is the extra information we have that allows us to determine the fake ball in 3 steps?
3 steps if you know the weight of the fake ball.
That's really it right.
Here is the solution in 3 steps which doesn't require previously knowing the weight of the fake:
>divide 6:6 A and B
>divide A into 3:3 A1 and A2
>divide B into 3:3 B1 and B2
step 1:
>weight A1 vs A2
step 2:
>if unequal equal: take A1 and measure against any 3 out of B2(which we now know to be all equal). This will tell us whether the fake is in A1 or A2 and whether it is heavier or lighter
>if equal: take B1 and measure against A1 which we now know to be equal. This will tell us whether fake is in B1 or B2 and whether it is heavier or lighter
step 3:
>from a group of 3 it is easy to know in one measure since now we know the weight of the fake
If A1 and A2 are equal, and you take B1 against A1 and also find them equal, how do you know anything about the fake in B2?
There is still a possible forth step there, because in step two if the measurement is equal, the outlier is in the fourth group, which hasn't been measured yet. If that happens, in step three the weight is unknown, requiring a fourth measurement to determine the weight.
Thus, there is a probability distribution that it will require 3 vs 4 steps.
Yeah I realized it just as I posted.
Google tells me that the answer is not actually a binary search but a mapping of the 3 possible configurations of the balance (>=
>If the first two groups don't weight the same, you have to make another measurement and you just lost 2 opportunities
What, why?
If you know it's heavier then clearly it's in the heavier sample - vice versa for lighter.
If the first two samples are equal weight, then the third sample is clearly the one with the ball.
balls
>>not 12 dicks
There are 12 dicks, one of these dicks has prostate issues that make it cum blood.
What fact can we know to find the bad tasting dick while swallowing at most three loads?
Most people don't realize that this is NOT binary search. You need to divide into 3 groups of 4 and then do individual manipulations, because you DO NOT know whether the fake ball is 1 g heavier or lighter. When you weigh 2 groups and the scales are uneven, which side is the fake ball in?
>If you know it's heavier
Yeah, and if you know which one's the fake you need to do zero steps
If it's any consolation, it didn't really click with me until I demonstrated it to myself with playing cards; 11 suited cards and one joker to be the fake.
>What is the extra information we have that allows us to determine the fake ball in 3 steps?
If the scales are balanced when you weigh 4 against 4, then you know the fake is in the untested 4 and you have 8 that you know are authentic that you can test against.
>6 on one side, 6 on the other, lighter side has the fake
>3 on one side, 3 on the other, lighter side has the fake
>2 on one side, 1 on the other, scale balances, side with 2 balls obviously has the fake or the lighter side has the fake since the 2 real ones will obviously peg the scale to their side
Simply putting the balls on the scale in the third step is enough to distinguish which one is fake, or will the OP come up with some stupid ass reason we're not allowed to touch the balls to put them on the scales in the first place?
Was that really so hard to figure it out?
>lighter side has the fake
You don't know if the fake is lighter or heavier.
First you need 3 steps to determine the outlier, then you need an extra step to determine if it's heavier or lighter. The only way to do it in three steps is if you get lucky, and the first 2 groups measured are equal.
The methodology still reduces the viable number of potentials to 2 with the same steps with reversed criteria.
It's not technically possible to do it in 3 steps, the 4th step would be choosing between the remaining two potentials to determine which one is the fake ball.
So now the OP gets to explain his or her methodology so we can tear that apart too.
1. 1234 - 5678,
2. 123 - 91011,
Take outlier group,
3a. 1 - 12, or
3b. 9 - 10,
2. 123 - 91011,
3a. 1 - 2,
3b. 567 - 91011
Can only distinguish outlier, not heavier/lighter.
>It's not technically possible to do it in 3 steps
It is if the first 4v4 weigh-in is balanced. You'd have 2 steps to determine the fake out of the remaining 4 balls. Easy.
No, you can do it in three steps if you get lucky.
1. Two groups of 4 measured equal, outlier is in third group
2. Take third group divide into two 3a and 3b
take 3a, and measure against 2 balls from the first measurement. If they are unequal you found whether the outlier is heavier or lighter.
3. in the third step, you divide 3a into half, and measure one ball again a control ball again. there, you found the outlier whether measured or not, and whether it was heavier or lighter.
>2 on one side, 1 on the other, scale balances, side with 2 balls obviously has the fake or the lighter side has the fake since the 2 real ones will obviously peg the scale to their side
How does this work? If the fake has any weight to it whatsoever the scale will always tip to the side with two balls regardless of where the fake is.
Thus, the minimum number of weighs is three based on probability, with maximum 4.
No. What he's saying is that if you weigh A and B and they're not the same, you can't jump right to the next step assuming that B has the different ball because it's heavier, because it's possible that the abnormal one is A with a lighter ball. This requires an additional step before reaching the second step on your algorithm and thus it won't be done in three steps. The only case where you can do it in three steps is when the group that's different is not on the balance on the first measuring, and that will only happen 1/3 of the times.
create 3 groups: (a1,a2,a3,a4), (b1,b2,b3,b4), (c1,c2,c3,c4)
compare (a1,a2,a3,a4) to (b1,b2,b3,b4)
1.if (a1,a2,a3,a4) heavier
1.target not in c
1.put two balls aside, get (a1,a2,a3), (b1,b2,b3)
1.swap 2 balls, get (a1,a2,b3), (b1,b2,a3)
1.swap a ball against a non target, get (a1,c2,b3), (b1,b2,a3)
1.compare (a1,c2,b3) to (b1,b2,a3)
1.1.if still (a1,c2,b3) heavier
1.1.target is a1, b1 or b2
1.1.compare (a1,b1) to (c2,c3)
1.1.1.if (a1,b1) still heavier
1.1.1.target a1 is heavier
1.1.2.if (a1,b1) lighter
1.1.2.target b1 is lighter
1.1.3.if (a1,b1) and (c2,c3) equal
1.1.3.target b2 is lighter
1.2.if (b1,b2,a3) heavier
1.2.target is a3 or b3
1.2.compare a3 to c1
1.2.1.if a3 heavier
1.2.1.target a3 is heavier
1.2.2.if equal
1.2.2.target b3 is lighter
1.3.if (a1,c2,b3), (b1,b2,a3) equal
1.3.target is a4,b4 or a2
1.3.analog to { 1.1.target is a1, b1 or b2 }
2.if (b1,b2,b3,b4) heavier
2.analog to { 1.if (a1,a2,a3,a4) heavier }
3.if (a1,a2,a3,a4), (b1,b2,b3,b4) equal
3.target within (c1,c2,c3,c4)
3.swap a ball against a non target (c1,c2,c3,a4)
3.compare (c1,c2) to (c3,a4)
3.1.if (c1,c2) heavier
3.1.target is c1,c2 or c3
3.1.compare (c1,c3) to (a2,a3)
3.1.1.if (c1,c3) still heavier
3.1.1.target c1 is heavier
3.1.2.if (c1,c3) lighter
3.1.2.target c3 is lighter
3.1.3.if (c1,c3) and (a2,a3) equal
3.1.3.target c2 is heavier
3.2.if (c1,c2) lighter
3.2.target is c1,c2 or c3
3.2.compare (c1,c3) to (a2,a3)
3.2.1.if (c1,c3) still lighter
3.2.1.target c1 is lighter
3.2.2.if (c1,c3) heavier
3.2.2.target c3 is heavier
3.2.3.if (c1,c3) and (a2,a3) equal
3.2.3.target c2 is lighter
3.3.if (c1,c2) and (c3,a4) equal
3.3.target is c4
3.3.compare c4 to a1
3.3.1.if c4 heavier
3.3.1.target c4 is heavier
3.3.2.if c4 lighter
3.3.2.target c4 is lighter
Nightmare mode
There are a prime number P > 7 balls.
Or you can just do it in 4 steps like a non retarded person would.
You failed the assignment, then. But congratulations on being non retarded.
Are you okay? Should I call someone?
>wight two random balls to make sure that they weight the same
>if so, it means that the different one isn't there. discard one of the balls
>now you have a non prime number and you can break it into many groups
Look up what a binary search is before you make yourself look like a retard for trying to look smart dumbass.
Moron. There are 3 possible results each time you do a comparison. Thus if you do 3 comparisons, you get 3^3=27 different cases, easily enough to cover 24 different cases of this assignment.
Maybe try thinking before talking out of your ass.
>Thus if you do 3 comparisons
That's why your defective method uses five comparisons right? HAHAHAHA I can't believe you're backpedaling this hard just to save face for making a mistake, maybe you can delete all your posts if you hurry, though I doubt you're even smart enough to figure out how to delete a post.
Ok so i am sorry if this turns into some kind of rant but i had an interview the other day for a webdesign job. I know my share of javascript and jquery but i'm not really a programmer. Anyway i thought it was ok because the job wasn't programming but design.
But the interviewer ask me if i can make a program that will print fuzz and bizz if the number is divisble by 3 and 5 and up to 100. wtf, i'm sure if i had access to google or stackoverflow i could've done it but no.. so i tell him i'm not sure about this question.
And THEN, the guy ask me a question like the OP but with only 8 balls, what the fuck ? I'm here for a webdesign job and the guy just flat out asks me question about binary search ??
Seriously i should've done a CS degree instead of my 3 years of experience working for a small startup, i would've learn all the unnecessary stuff that no one ever use in the real world.
Either this is the worst bait I have ever seen, or you are just to stupid to read.
There are clearly different branches, along each branch there are at most 3 comparisons.
Ez. Pick up all the balls one by one and the heavier or lighter one you should be able to feel. Put that one on the scale to confirm... BOOM. Ez. Got it in one turn. I'm an arts major. This is why you nerds need people like me to think outside the box. This is why apple was useless without Steve jobs.
Start by dividing the balls up to 3 groups. You can cut down the possible balls to 4 in the second step this way. From there just measure 2 balls, if both are "normal" you have a worst case scenario that needs another weighing. If one of them is fake you solved it in 2 steps.
>weighing with my hands is not weighing
>I should be able to distinguish a 999g ball from a 1kg ball, by hand
>I'm an arts major
samefag
>can't recognize a joke when he sees one
Autism confirmed.
samefail
>I was only pretending to be retarded
>Either this is the worst bait I have ever seen, or you are just to stupid to read.
No, your algorithm is defective according to your 3 step claim and I can prove it. When you are on:
>1.compare (a1,c2,b3) to (b1,b2,a3)
If those both measure equal, then the abnormal ball can be a2, a4, or b4, and there is no way to solve it with the 1 measurement you have left; it will take two additional measurements, thus making it 4 steps. You failed to account for the worst case scenarios like above several times, yet you are so sure that your algorithm is perfect, you are pretty fucking stupid mate. You don't measure algorithms based on only the best case possible.
>1.3.if (a1,c2,b3), (b1,b2,a3) equal
>1.3.target is a4,b4 or a2
>1.3.analog to { 1.1.target is a1, b1 or b2 }
>he didn't answer the question
Say how to you solve it measuring just one more time. You already measured two out of three times. You can't.
this took me longer to draw than to figure out, if you can't figure this out you are a retard. I drew your example in 4 tries and 3 tries
i think i had this question in an exam paper once
After
>1.if (a1,a2,a3,a4) heavier
You have the information that a4 and a2 were on the heavier side, and that b4 was on the lighter side.
Furthermore you have the information that c1,c2,c3,c4 can be used as control group.
Thus we compare (a4, b4) to (c2, c3).
If (a4, b4) is heavier than (c2, c3), then it's due to a4 being heavier.
If (a4, b4) is lighter than (c2, c3), then it's due to b4 being lighter.
If they (a4, b4) and (c2, c3) are equal, then it's due to a2 being heavier.
...
See? All you had to do was not to type like a fucking autist. It's amazing just how dense you are that I have to bait you into typing it normally. Retard.
Except the odd ball can be heavier or lighter so you can't distinguish which group contains the odd ball in step two of the 3 tries method.
What the fuck!? So even when you realize you were wrong, you still continue to insult me? Fuck off, I'm done here.
Measure ABCD - EFGH
Case 1 - imbalanced:
------------------------------------
ABCD > EFGH => λ µ β verified to be good
Measure ABCH - λµβC
Case 1:
ABCH > λµβD => A B or C too light, trivial
Case 2:
ABCH = λµβD => E F or G too heavy, trivial
Case 3:
ABCH < λµβD => H too heavy or D too light, measure H - λ
Case 2 - balanced:
------------------------------------
ABCD = EFGH => λ µ β verified bad, AB verified good
Measure λµ - AB
Case 1:
λµ > AB => λ or µ too light, trivial
Case 2:
λµ = AB => β too light or too heavy, trivial
Case 3:
λµ < AB => λ or µ too heavy, trivial
Fuggg I mixed C and D, should be λµβD in the second measurement in case 1
oh fuck i read that wrong. welp i guess i didn't get the job :3
This Also on the first time you compare it would be harder if the ball was in the balance, it being outside is the easier of cases.
why did you repeat someone else's post by quoting it? if you didn't think that I could see his reply, how would you expect me to see your reply?
>if you can't figure this out you are a retard
>doesn''t even understand the problem
lmao
You're still wrong though, I was baiting into expressing your line of thought in a normal fashion to see what you though you knew, and you did, but it's still wrong. In the very first measuring if both groups are equal then the ball is in the outer one. Then you measure the halves against each other and one will be heavier. At this point there is no way to figure out which one is the ball in just the 1 comparison that you have left. You can't apply the method you described before to this case. This is the truly worst case scenario and it takes 4 comparisons, not 3. Consider your algorithm refuted queer.
Can we agree that this is correct or is there a flaw
The different ball changes color after it is weighed three times.
>I was baiting
Well, you would have to first know whether the ball is heavier or lighter, only then can I see this being solvable at worst in 4 steps, but I might be wrong...
Let's assume the odd ball is heavier, so we start by separating the balls into 2 groups:
1 2 3 4 5 6 - 7 8 9 10 11 12
If the right side is heavier than the left one, we take that group, half it, and repeat the process:
7 8 9 - 10 11 12
If the right side is heavier again, we know one of the balls there is the odd one.
Now we can weight 1 ball against 2 balls, for example:
10 - 11 12
If we get lucky, the ball on the left (10) will weight more than half of the 2 balls on the right combined, then we have solved it in 3 steps.
If not, then the odd ball is either 11 or 12, so we have to weight each one alone and see which one it is, that being step 4, the worst case scenario.
This is also basically a binary search tree, where you eliminate half of the data based on a recursive comparison until you reach the answer.
You know what's faster than binary search? Hashing. The 3 step solution is essentially that.
What if the defect ball is lighter rather than heavier?
Then you pick the group that weighs less :)
10kg - 20kg
If you're looking for lighter, pick the left side. If you're looking for heavier, pick right side.
It's a simple larger/smaller than test.
How do you know that you are looking for a lighter ball? In the OP it is stated that the defect ball may be lighter or heavier, and you're supposed to both find the defect ball and state whether it is lighter or heavier.
It's impossible unless you know what you're looking for, otherwise you must check every single ball until you find the odd one, and if it happens to be the last ball, then your algorithm will take the longest.
If it happens to be the first, you will check at most 2 balls, because even if the first one is the odd one, you need to check another ball to know what the normal weight is.
Divide into 4 groups of 3, weigh them with 2 other group of 3.
After 2-3 tries you know which group has the heavier/lighter ball. Take 2 of the 3 balls in that group and weigh them.
>I can't refute his refutation so I'll just point the fact that he lowered himself to my intellectual level to get me to speak my ideas clearly in order to attack them, and then I will be proud about yea
You're still wrong and still retarded, nice argument fag.
You don't really expect an answer after the way you just behaved, do you. Kill yourself, you piece of shit.
see
you might simply swap identical balls and waste a step
I saw that, but your answer scares the children, so it's not a good one in my book.
If I had a teacher like that, it would demotivate me from learning. We should make it clear and easy to understand, not use cryptic math symbols to convey a simple idea to someone.
>I can't refute what you said and prove that my algorithm is right, therefore I will pretend to have some sort of moral high ground to safe face and avoid saying that I was wrong
I don't give a shit about how you feel, it's not about that; if you're gonna cry better go do it elsewhere. Here only logic matters and I'm gonna repeat the part that you can't solve just because I know that it hurts your pride realizing that you were wrong in a Malaysian puppeteering and ventriloquism forum. Here it comes, brace for it queer:
>In the very first measuring if both groups are equal then the ball is in the outer one. Then you measure the halves against each other and one will be heavier. At this point there is no way to figure out which one is the ball in just the 1 comparison that you have left. You can't apply the method you described before to this case. This is the truly worst case scenario and it takes 4 comparisons, not 3. Consider your algorithm refuted queer.
What if the ball is just a fraction of a gram heavier or lighter? A simple mechanical balance wouldnt have the needed accuracy to detect the fake ball no matter how many weighings.
I dunno, I could've tried to use ascii art but Cred Forums would probably have mangled it. At any rate I'm not a teacher.
Hehe, it's alright
>At any rate I'm not a teacher.
You said it bro, teaching is a skill by itself. I'm just a developer too, not a teacher.
>Here only logic matters
Hahahahahaha. The irony of this retard sprouting that while being too stupid to understand a solution laid out in front of him.
That's not irony, that's just more low quality bait
You're actually retarded
only takes three weighs, worst case, actually
Look at yet another reply that's 100% ad hominem and 0% proof. I'm gonna repeat it again just because I can tell from your posts that being wrong really makes you mad:
>In the very first measuring if both groups are equal then the ball is in the outer one. Then you measure the halves against each other and one will be heavier. At this point there is no way to figure out which one is the ball in just the 1 comparison that you have left. You can't apply the method you described before to this case. This is the truly worst case scenario and it takes 4 comparisons, not 3. Consider your algorithm refuted queer.
I see. My bad.
I'll find and kidnap the ball manufacture and the the questioner, and put them in a grimy basement. First I let them starve for a couple of days, then I'll drag them into the same room and tie them to a chair opposite of each other. While telling them I need to identify the fake ball and one of them is going to tell me which it is, I will douse them both with gasoline. When I'm done I'll light a zippo asking them "so who of you want to live?". The last one to open his mouth will get the zippo thrown in his lap. When the other one has spilled the beans and identified the ball, I'll burn him as well.
As you can see I'm quite good at social engineering.
I see. This is the same as if you were given 4 balls + reference balls and asked to find the different one with only 2 comparisons. In any given comparison there are 3 possible outcomes but you only have two tries so 2^3=8 which is only half of what you need to cover all possible cases. It's impossible to do in 2 comparisons and since the 12-balls-3-comparisons scenario can transpose into this one after the first comparison in the worst of cases it's also impossible to solve it in 2+1 comparisons. You need an extra comparison to make it happen. I think this wraps up the thread pretty nicely, thanks for bothering to get that right. Polite sage.
/thread
If you're so sure 3 comparisons aren't enough tell us why this is wrong:
KEEP THIS THREAD ALIVE I WILL DRAW A FLOWCHART PROVING THE METHOD I READ IT WRONG DOOD
>This is the same as if you were given 4 balls + reference balls and asked to find the different one with only 2 comparisons
You are asked to determine if the outlier is heavier or lighter than the other balls.
The solution to this is given >A,B,C,D,E,F,G,H
>lambda, mu, beta
What happened to 12 balls?
It's a trick question because scales don't work that way.
Place one ball on each side.
If they measure the same, add two more until you run out.
If they are unequal, one of the last two balls you added must be the fake.
No need to remove any balls from the scale unless it's the last two.
I've got two balls for you to weight right here m8
I'm registering 0.00 grams here
You can do this in zero weighings by just hefting the balls in your hand. You should know a lot about that.
yeah theyre inside ur mom right now give me 15 minutes to pull them out and you can try again
I DID IT FUCK YOU ALL
I'm not drawing the other side of the graph, OP can figure that part out if it's actually for a grade... can't make it too easy on him.
did you use yed?
if yes care to share the graphml?
I did use yed, and i'm not gonna give anyone any answers in an easily usable format lol. that would be cheating :3 you can do it too it wasn't too difficult
Someone take a screenshot of this and put a cs degree pic on it, please.
the "answer" is right there
you're just saving somebody from redrawing the whole fucking diagram, which has zero intellectual value added
thanks anyways
why do you want to draw the other side of the graph?
meh
I was wondering what the flowchart auto layout would look like, without groups at first, and then with groups around each of the two major branches
care to upload images of that at least?
Three steps:
Weigh 6 and 6
Divide the heavier into 3 and 3 and weigh
Take the heavier, hold one ball out and weigh the two remaining - if they're equal, you're holding the heaviest, otherwise it's the one that tips the scales
its simple method
u weight 3 balls and 3 balls
if they are ok u discard
then u weight other 2 and leave the other there
if they are same weight left one is bad ball
if they arent same u take one and weight with the original 6 if they are ok then the other one is the bad ball u can tell if its lower of higher cause u know the right original is ok weight
now if they original 6 u weight are bad now it get tricky
u take of those u take 2 apart (one from each side)
and take 2+1 good ball and the other side u weight 2+1 good ball
if they ok u weight other 1 of the 2 balls with good ball then u know
now if those 2+1_2+1 are bad u take the good ball out and then u weight 1 bad and 1 good on each side o fuck u need 4 for this
First we weigh {1,2,3,4} on the left and {5,6,7,8} on the right. There are three scenarios which can arise from this.
If they balance, then we know 9, 10, 11 or 12 is fake. Weigh {8, 9} and {10, 11} (Note: 8 is surely not fake)
If they balance, we know 12 is the fake one. Just weigh it with any other ball and figure out if it is lighter or heavier.
If {8, 9} is heavier, then either 9 is heavy or 10 is light or 11 is light. Weigh {10} and {11}. If they balance, 9 is fake (heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {8, 9} is lighter, then either 9 is light or 10 is heavy or 11 is heavy. Weigh {10} and {11}. If they balance, 9 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
Phwww, that was confusing enough but we are not done yet.
1/3
sure :3 honestly i don't care you can have the file, as long as YOU post pics as well!
If {1,2,3,4} is heavier, we know either one of {1,2,3,4} heavier or one of {5,6,7,8} is lighter but it is guarantees that {9,10,11,12} are not fake. This is where it gets really tricky, watch carefully. Weigh {1,2,5} and {3,6,9} (Note: 9 is surely not fake).
If they balance, then either 4 is heavy or 7 is light or 8 is light. Following the last step from the previous case, we weigh {7} and {8}. If they balance, 4 is fake(heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {1,2,5} is heavier, then either 1 is heavy or 2 is heavy or 6 is light. Weigh {1} and {2}. If they balance, 6 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
If {3,6,9} is heavier, then either 3 is heavy or 5 is light. Weigh {5} and {9}. They won’t balance. If {5} is lighter, 5 is fake (lighter). If they balance, 3 is fake (heavier).
2/3
If {5,6,7,8} is heavier, it is the same situation as if {1,2,3,4} was heavier. Just perform the same steps using 5,6,7 and 8. Unless maybe you are too lazy to try and reprocess the steps, then you continue reading the solution. Weigh {5,6,1} and {7,2,9} (Note: 9 is surely not fake).
If they balance, then either 8 is heavy or 3 is light or 4 is light. Following the last step from the previous case, we weigh {3} and {4}. If they balance, 8 is fake(heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {5,6,1} is heavier, then either 5 is heavy or 6 is heavy or 2 is light. Weigh {5} and {6}. If they balance, 2 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
If {7,2,9} is heavier, then either 7 is heavy or 1 is light. Weigh {1} and {9}. If they balance, 7 is fake (heavier). If they don’t balance then 1 is fake (lighter).
3/3
sweet, thanks!
I'm on it
Auto layout:
meh/10
Auto layout after grouping:
meh/20
hierarchy layout is best d e s u
12 balls would mean 6 dicks on average
yeah I'm on it
still not ideal
Hierarchical with groups
Hierarchical with 2 layers of groups
this one turned out the best, trips confirms it
>simple binary search tree algorithm
>flowcharts and fights
Cred Forums, I'm disappoint
My solution:
>Divide the 12 in 3 groups of four. Find the odd group.
>Split the odd group in two, you should already know if the odd ball is heavier or lighter.
>You'll have 2 balls now find th heavier or lighter one.
Correct me if I did something bad.
But binary search requires knowing what to look for. The problem is that it can be either lighter or heavier than a normal item.
my flowchart is beautiful thank you very much
>>you should already know if the odd ball is heavier or lighter.
How?
This would work as well:
1. Divide into two groups of six
2. Divide into two groups of three
3. Weigh 2 of the remaining three; if they weigh the same amount, the third is the odd one out
Compare the 3 groups to one other? 2 groups are the same, 1 is e.g. heavier. Which means that the odd ball is heavier.
This thread makes me sad.
You guys do understand that if you measure 4 with 4, you know EXACTLY which group of 4 has the fake ball right?
Not if you don't know if the fake ball is lighter or heavier
How so? When comparing the groups you get back whether or not a group is heavier or lighter.
This is the easiest way. /tech/ is officially retarded.
>1. Divide into three groups of four, weight 2 groups
You don't know which is the outlier because the outlier could be lighter or heavier. Disqualified.
Ex: Groups 1, 2 ,3. Weight of 1 is 4.5g and 2 is 4.6g. No way to tell which of three groups has the odd ball because you don't know if it's heavier or lighter
Practically,
>Divide into 3 groups and weigh all three, can stop at two if the first two are equal.
>The two groups with the same weight give the weight of one ball (Group/4).
>Weigh each of the remaining 4 balls in the odd group to find the faggot
Minimum three data collections and one division problem
Maximum seven data collections and one division problem
You're officially retarded, see
That's still no reason to have 4 weighings.
>weigh 12 balls 6 by 6
>weigh 4 balls out of lighter/heavier 6 2 by 2
>weigh remaining 2 balls
with step 2 or 3 you should get your answer
over 9000 hrs in ms paint
You could go 2 and 2 for the odd group of four, but practically speaking I'd rather just gamble on getting it right on the first single weighing
drop them all and see which one has a different bounce characteristic
Weight the 3 groups of balls, note the weight that is equal in two groups. Divide that weight by 4 and you get the weight of a single Ball. From there it is easy
2 l8 m8