//-------------------------------------------------------------------
// enigma1346.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "Divide into Primes" from "New Scientist", 25 June 2005, page 56
//
// Eight coins with denominations 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p,
// are divided between two people. Each person has at least two coins,
// and each person's monetary total is a prime.
//
// You ask one of the persons:
// "Do you have x number of coins?" and the answer is "No."
// You then ask:
// "Do you have the y pence coin?" and the answer is "Yes."
//
// For some x, y, those answers are sufficient for you to determine
// the monetary value of that person's coins. What is it?
//
// Let's use the lower 8 bits of an integer to represent the coins
// a person has, where the least significant bit is the 1p coin.
// For example, the integer 13 is the bits 1101, which indicates
// possession of the 1p, 5p, and 10p coins.
//
// In all these functions, the integer iBits will represent this
// number. The integer ~iBits represents the other person's coins,
// if only the bottom 8 bits are considered.
#include
// This function counts the number of coins by counting the number
// of 1 bits in the bottom 8 bits of iBits.
int NumCoins(int iBits)
{
int i, iSum = 0, iMask = 1;
for (i = 0; i < 8; i++)
{
if ((iBits & iMask) != 0)
iSum ++;
iMask <<= 1;
}
return iSum;
}
// This function is similar except that it returns the total
// monetary value of the coins.
int CoinSum(int iBits)
{
int iPence[] = { 1, 2, 5, 10, 20, 50, 100, 200 };
int i, iSum = 0, iMask = 1;
for (i = 0; i < 8; i++)
{
if ((iBits & iMask) != 0)
iSum += iPence[i];
iMask <<= 1;
}
return iSum;
}
// Also required is a function that indicates if a number
// is prime.
int IsPrime(int i)
{
int j = 2;
if (i < 2)
return 0;
while (j * j <= i)
{
if (i % j == 0)
return 0;
j += 1;
}
return 1;
}
// It is now possible to determine which distributions of the eight
// coins result in each person getting at least 2 coins, and each
// person's monetary value being prime. The following code (which is
// commented out) prints just one person's monetary value.
// The total of the two persons is always 388.
/*
int main(void)
{
int iBits;
for (iBits = 0; iBits < 256; iBits++)
{
if (NumCoins(iBits) > 1 && NumCoins(~iBits) > 1 &&
IsPrime(CoinSum(iBits)) && IsPrime(CoinSum(~iBits)))
printf("%i\n", CoinSum(iBits));
}
return 0;
}
*/
// If you uncomment, compile, and run that code -- you'll also need to
// comment out the main function below -- you'll find 8 possibilities,
// which are:
//
// 71 = 1 + 20 + 50
// 107 = 1 + 2 + 5
// 131 = 1 + 10 + 20 + 100
// 137 = 2 + 5 + 10 + 20 + 100
// 251 = 1 + 50 + 200
// 257 = 2 + 5 + 20 + 200
// 281 = 1 + 10 + 20 + 50 + 200
// 317 = 2 + 5 + 10 + 100 + 200
//
// There are 3 possibilities where there are 3 coins,
// 2 possibilities where there are 4 coins, and
// 3 possibilities where there are 5 coins.
//
// Your first question "Do you have x number of coins"
// eliminates either 2 or 3 of these possibilities, and
// the second question "Do you have the y pence coin?"
// gives you the conclusive information.
//
// In other words, if you eliminate the 3-coin possibilities,
// you're looking for a coin that shows up in only one of
// those that are left. If there is no unique coin, try
// considering only the 3-coin and 5-coin possibilities,
// and then (if that doesn't work) try the 3-coin and
// 4-coin possibilities.
//
// Cutting to the chase:
//
// The solution comes about when the first question is
// "Do you have 5 number of coins?" (The answer, remember,
// is "No") and the second question is "Do you have the
// 10p coin?" to which the answer is "Yes." The person has
// coins that total 131p.
//
// Or, we can write a program that does this work for us.
int main(void)
{
int iNumSkip, iNum, iBits, iUnique, iNotUnique;
// iNumSkip is x in the question "Do you have
// x number of coins?" It has to be between 2 and 6.
for (iNumSkip = 2; iNumSkip < 7; iNumSkip++)
{
// The lowest 8 bits of the following two variables
// will keep track of the unique coins in all
// the remaining possibilities.
iUnique = iNotUnique = 0;
// Loop through the number of coins.
for (iNum = 2; iNum < 7; iNum++)
{
// But skip the one equal to iNumSkip.
if (iNum == iNumSkip)
continue;
// Now loop through the possible distributions
// of coins.
for (iBits = 0; iBits < 256; iBits++)
{
// We're looking for a number of coins
// that equals iNum, and both person's coins
// adding up to a prime number.
if (NumCoins(iBits) == iNum &&
IsPrime(CoinSum(iBits)) &&
IsPrime(CoinSum(~iBits)))
{
// If a bit in iBits is set, and a bit
// in iUnique is set, that coin is
// actually not unique.
iNotUnique |= iBits & iUnique;
// Adjust iUnique for the actual coins,
// but don't allow coins already flagged
// as not unique.
iUnique |= iBits;
iUnique &= ~iNotUnique;
}
}
}
// At this point, if iNumSkip is the number of coins
// in the first question, then iUnique should have
// just 1 bit set, which is the value queried in the
// second question.
//
// Let's first check that iUnique has only 1 bit set.
if (NumCoins(iUnique) != 1)
continue;
// if that test is passed, we'll loop through again,
// and now find the distribution where the iUnique bit is set.
for (iNum = 2; iNum < 7; iNum++)
{
if (iNum == iNumSkip)
continue;
for (iBits = 0; iBits < 256; iBits++)
{
// Notice the first clause.
if ((iUnique & iBits) &&
NumCoins(iBits) == iNum &&
IsPrime(CoinSum(iBits)) &&
IsPrime(CoinSum(~iBits)))
{
printf("%ip", CoinSum(iBits));
}
}
}
}
return 0;
}