How to tackle this puzzle? [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

Disclaimer: This is not a homework problem. I stumbled upon this puzzle here and I also have the answer. However, I am not able to figure out an approach to arrive at the solution.

The puzzle is as given below:

The product of the ages of David's children is the square of the sum of their ages. David has less than eight children. None of his children have the same age. None of his children is more than 14 years old. All of his children is at least two years old. How many children does David have, and what are their ages?

The answer happens to be 2,4,6,12.

Please suggest a way to solve this problem programmatically.

Answer 1

I solved it in java using a recursive approach. First the program prints all the combinations, then gives the correct combination (that matches the specified criteria) at last.

This program instantly gives the output

(2, 4, 6, 12)

just as you have specified in your question.

public class Tackle {
static int[] ages = {2,3,4,5,6,7,8,9,10,11,12,13,14};   // Since the program uses a recursive function,
static StringBuffer sb = new StringBuffer("");          // the variables are declared as static
static int x=0,occurances=0;
static int sum,pdt=1,count=0;
static String[] instances = new String[100];
static void recurse(int a[], int k, int n) throws Exception
{
    if(k==n)    // This program obtains various combinations using binary technique
    {
        for(int i=0;i<n;i++)
            if(a[i] == 1){
                    System.out.print(ages[i]+" ");   // Displays all the combinations available             
                    sum = sum + ages[i];
                    pdt = pdt * ages[i];  
                    count++;                                        
                    sb.append(String.valueOf(ages[i]+" "));
                    }
                    if(Math.pow(sum, 2) == pdt && count<8){     // Checking the criteria
                        instances[occurances++] = sb.toString();
                    }

                    sb = new StringBuffer("");
                    count = 0;
                    sum = 0;
                    pdt = 1;
                    System.out.println("");
    }
    else for(int i=0;i<=1;i++)
    {       
        a[x++] = i;
        recurse(a,k+1,n);
        x--;
    }
}

public static void main(String[] args) throws Exception {
    int[] a = new int[10000];
    recurse(a,0,ages.length);
    if(occurances>0)
    {
        System.out.println("No of combinations matching: " + occurances);
        for(int i=0;i<occurances;i++)
        System.out.println("The combination of ages is [ " + instances[i] + "]");
    }
    else
        System.out.println("No combination matches the criteria. ");
}
}

The output obtained was

[All possible combinations are listed here]
No of combinations matching: 1
The combination of ages is [ 2 4 6 12 ]

Answer 2

In Python (Which is not what you asked, but you're more asking for an algorithm):

import operator
import itertools

possible_ages = range(2,15)

# If the list of ages passed to this function returns true, then this solves the puzzle.
def valid(ages):
    product_of_ages = reduce(operator.mul, ages, 1)
    square_of_sum_of_ages = reduce(operator.add, ages, 0) ** 2
    return product_of_ages == square_of_sum_of_ages

for number_of_children in range(1, 9):
    for ages in itertools.combinations(possible_ages, number_of_children):
        if valid(ages):
            print ages

And that prints, almost immediately:

(2, 4, 6, 12)

Answer 3

You don't specify that the ages are all integers, but I'm going to assume that's true. If so, there are only about 1e9 possible combinations of those ages among 8 children. Simply enumerate (for(age1=2; age1<15; age1++) { for(age2=2; age2<15; age2++) { ...) them all and test. Your computer should finish that task within a few minutes even in a script interpreter.

There are optimizations to be applied, because hard-coding "8" loops is clumsy, and because the age lists are order-independent (having children of "4 and 2" is the same thing as "2 and 4"), but frankly I don't think that's worth it here. Your time taken coding the extra steps will take more time than you'll save at runtime.