# generic fake coin problem

Ryan McGuire

Ranch Hand

Posts: 1078

4

posted 4 years ago

Are you expecting an algorithm that solves the puzzle in full generality?

e.g.

The initial problem with that would be to identify all the assumptions that make a difference to the algorithm. I'm certainly not saying that first step is insurmountable. However, I don't currently see an obvious way to know when you've covered all the possibilities.

I could see starting with a few different sets of assumptions, working out the algorithm for each and then trying to identify the common structure of the algorithm and the parts that rely on the assumptions.

By the way, I'm still thinking about this problem from time to time, but I haven't really put pencil to paper yet.

Steve Fahlbusch wrote:now just be clear, the above can not be solved, but....

provide a constraint so that your algorithm will work.

eg: given that all fake are larger, or all fake are smaller or half have are larger and half fake are smaller.

The constraint determines the algorithm.

Are you expecting an algorithm that solves the puzzle in full generality?

e.g.

The initial problem with that would be to identify all the assumptions that make a difference to the algorithm. I'm certainly not saying that first step is insurmountable. However, I don't currently see an obvious way to know when you've covered all the possibilities.

I could see starting with a few different sets of assumptions, working out the algorithm for each and then trying to identify the common structure of the algorithm and the parts that rely on the assumptions.

By the way, I'm still thinking about this problem from time to time, but I haven't really put pencil to paper yet.

Kyupa Supa

Ranch Hand

Posts: 30

peopalove tzer

Greenhorn

Posts: 2

posted 3 years ago

contraint #1: given that all fake are larger

function findfake(){

var coins[n]

var smallest

for(i=1,smallest=coins[0];i<n;i++){

if(coins[i].size < smallest.size){

smallest = coins[i];

}

}

return smallest;

}

contraint #2: half fake have are larger and half fake are smaller

function findfake(){

var coins[n]

if(n isEvenNumber){

return "no real coin";

}else{

sort(coins[], size)

return coins[roundup(n/2)];

}

}

Is this what you mean?

function findfake(){

var coins[n]

var smallest

for(i=1,smallest=coins[0];i<n;i++){

if(coins[i].size < smallest.size){

smallest = coins[i];

}

}

return smallest;

}

contraint #2: half fake have are larger and half fake are smaller

function findfake(){

var coins[n]

if(n isEvenNumber){

return "no real coin";

}else{

sort(coins[], size)

return coins[roundup(n/2)];

}

}

Is this what you mean?