Problem

You are given 12 identical balls, one of which is slightly heavier or lighter than the rest. (All other are of exactly each weights)

You are also given a balance scale to use. Write an algorithm for identifying the defective ball using that scale minimum number of times.

This is achievable in 3 usage. In an ideal scenario we will never need to use the balance more than 3 times to know exactly which ball is defective and also to know whether its heavier or lighter.

Can you find a way to do so?

Solution

The first trick is to realize that the balance scale don’t give us binary information but it gives us one extra information. It just doesn’t tell us the left is heavier or the right, it also tells if the things are of equal weight. So if we use the scale smarty we can exploit this property of the scale and achieve our goal.

Another approach while finding the solution is to not get lost in the rabbit hole. We should early reject some of the ideas we try in hit and trial. To early reject something we need to see the redundancy in the method or a lost oppertunity.

So if we see that when using the scale for some use case it is giving us the already known information or even not giving us a good amount of information (at least 3 points of information we should get (defining information is tricky here, we’ll have to get a feel for it)) then its a lost cause and we can reject that idea early on.

We should also build a few things bottom top. Keep your answers ready for small use cases, for 2, 3, 4 balls etc. This will give you a connection point while you are deep inside the rabbit hole and you will save you a few backtracks.

Algorithm

The one algorithm I found is given shape in this cpp code. It also tests all the 12*2 = 24 use cases and prints the result for those.

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;
int faulty;

int balance(const vector<int> &vl, const vector<int> &vr){
	// 1 means first param heavy
	// 2 means invalid measurement
	if(vl.size()>6||vr.size()>6)	return 2;
	unordered_set<int> l(vl.begin(), vl.end());
	unordered_set<int> r(vr.begin(), vr.end());
	if(l.size()!=vl.size()||r.size()!=vr.size())	return 2;
	unordered_set<int> o(vl.begin(), vl.end());
	o.insert(vr.begin(),vr.end());
	if(o.size()!=l.size()+r.size())	return 2;
	if(l.size()>r.size())	return 1;
	if(l.size()<r.size())	return -1;
	if(l.find(faulty)!=l.end()||r.find(-faulty)!=r.end())	return 1;
	if(l.find(-faulty)!=l.end()||r.find(faulty)!=r.end())	return -1;
	return 0;
}
pair<int,int> puzzle_12(){
	// return value:
	// {faulty_index, heavy/light}
	// heavy: 1, light: -1
	
	vector<int> o = {12,1,2,3};
	vector<int> b = {4,5,6,7};
	vector<int> h = {8,9,10,11};
	
	int x = balance(b,h);	// 1 means first heavy
	if(x==-1)	swap(b,h);
	if(x){
		o.push_back(h[3]);
		h[3] = b[3];
		h.push_back(b[2]);
		x = balance(h,o);
		if(x==1){
			h = {b[3]};
			b = {b[2]};
			x = balance(b,h);
			if(x)	return {x==1?b.back():h.back(),1};
			else	return {o.back(),-1};
		}
		else if(x==-1){
			o = {h[1]};
			b = {h[2]};
			x = balance(o,b);
			if(x)	return {x==1?b.back():o.back(),-1};
			else	return {h[0],-1};
		}
		else{
			o = {b[0]};
			h = {b[1]};
			x = balance(o,h);
			return {x==1?o.back():h.back(),1};
		}
	}
	else{
		int O = o.back();
		o.pop_back();
		int B = b.back();
		b.pop_back();
		x = balance(o,b);
		if(x){
			int X = x;
			O = o.back();
			o.pop_back();
			b = {o.back()};
			o.pop_back();
			x = balance(o,b);
			if(x)	return {x==X?o.back():b.back(),X};
			else	return {O,X};
		}
		else{
			o = {O};
			b = {B};
			x = balance(o,b);
			return {O,x};	// 1 means heavy
		}
	}
}
int main() {
	pair<int,int> p;
	for(faulty=-12; faulty<=12; faulty++){
		if(!faulty)	continue;
		p = puzzle_12();
		cout<<"Ball at index "<<p.first<<" is "<<(p.second==1?"heavy":"light")<<endl;
	}
	return 0;
}

Ideone it!