13
$\begingroup$

The sum of the ages of my five daughters is 43. The ages of any two of them have a common factor greater than 1. How old are my daughters?

$\endgroup$
  • $\begingroup$ The number of partitions of a number (such as this partition of 43) that can be recovered uniquely from their graph of common divisors (or P-graph) are counted in oeis.org/A298676. $\endgroup$ – Bernardo Recamán Santos Jan 29 '18 at 1:39
17
$\begingroup$

Not sure if it's unique, but this works:

15, 10, and triplets of 6 years old.

The common factors:

2, 3 and 5.

How I found it:

Starting from the fact that any two have a gcd greater than 1, I assumed that all three have exactly two small prime factors. I assumed at least 2 and 3 for those. Starting with 6, 6 and 10, I had 21 years left, which can come from 6 and 15.

$\endgroup$
  • $\begingroup$ The difference between 2 of the triplets is still factor 1? how would that work? $\endgroup$ – Totumus Maximus Dec 21 '17 at 16:01
  • 3
    $\begingroup$ The question states they must have a common factor greater than 1, which they have. They have three, even: 2, 3 and 6 $\endgroup$ – Lolgast Dec 21 '17 at 16:06
  • $\begingroup$ Ok, I guess my mind is just a bit boggled about this then. $\endgroup$ – Totumus Maximus Dec 21 '17 at 16:09
  • 2
    $\begingroup$ @TotumusMaximus GCD(6,6) = 6, not 1. $\endgroup$ – Jaap Scherphuis Dec 21 '17 at 16:27
19
$\begingroup$

Here is another solution. Your daughters are ages

43, 0, 0, 0 and 0 (congratulations on your new-born quadruplets!).

This works, because

zero is divisible by every non-zero integer, and therefore all five ages share the common divisor 43.

$\endgroup$
  • 3
    $\begingroup$ That's cheating! But very clever. $\endgroup$ – cwallenpoole Dec 21 '17 at 17:14
  • 2
    $\begingroup$ This answer is almost a winner but is not valid. Because they don't share a divisor, they share a factor. you cannot factor those [spoiler] numbers together, so this is not valid. $\endgroup$ – Mindwin Dec 21 '17 at 19:46
  • 3
    $\begingroup$ @Mindwin 43 is a factor of itself and is also a factor of 0. We have 0=43*0. $\endgroup$ – drhab Dec 22 '17 at 8:26
  • 3
    $\begingroup$ @Mindwin I agree that 0 does not have a prime factorization, but it seems to me that 0 = 43*0 is still a factorization of 0, just like 24 = 4 * 6 is a factorization of 24 (just not a prime factorization). $\endgroup$ – Marc Paul Dec 22 '17 at 12:03
  • 2
    $\begingroup$ @MarcPaul Ok. I'll nail this as a lack of rigour on the puzzle. It indeed does not say nothing about prime factoring. $\endgroup$ – Mindwin Dec 22 '17 at 14:47
13
$\begingroup$

Your daughters are

6, 6, 6, 10, and 15

It is obvious that the sum of those ages is 43. For each pair the common factors are:

gcd(6, 10) = 2, gcd(6, 15) = 3, gcd(10, 15) = 5, and gcd(6, 6) is obvious.

The only remaining question is whether that is the only possible solution. My first observation was that

43 is a prime thus the ages cannot all have a single prime factor in common.

I also realized that since each pair have a common factor

There must be at least 3 different prime factors involved such that each pair can share a factor without all three sharing a factor. (If there were only 2 factors involved one of them would have to be shared among all the daughters or there would be a pair of daughters not sharing a factor).

The smallest sum we can achieve is by using

The three smallest primes as factors making the possible ages 6, 10, and 15. And there would have to be three of age 6 for a total of five daughters. Any other approach will result in a larger sum than 43.

$\endgroup$
  • $\begingroup$ While I'm also convinced that there's just one solution, I'm not sure your proof is completely rigorous, specifically the part of requiring at least 3 factors. What would the problem, in case of 2 factors, be with one factor being shared among all of them? $\endgroup$ – Lolgast Dec 22 '17 at 8:14
  • $\begingroup$ @Lolgast If $p$ is a common factor of $n_1,\dots,n_5$, then $p\mid n_1+\dots+n_5=43$, so $p=43$. But then the sum is at least $5\cdot 43$. $\endgroup$ – Mario Carneiro Dec 22 '17 at 8:20
  • $\begingroup$ So in the case of two factors $p,q$, there is one child omitting $p$ and another child omitting $q$, and that pair of children has a gcd omitting both. $\endgroup$ – Mario Carneiro Dec 22 '17 at 8:25
  • $\begingroup$ @MarioCarneiro Ah of course... I should've thought of that. Guess I'm not fully awake yet. $\endgroup$ – Lolgast Dec 22 '17 at 8:29
  • 2
    $\begingroup$ An emphatic +1. IMHO, this should be the accepted answer, because (1) it was posted first (although, peculiarly, it was flamboyantly wrong at first), and (2) it has a better explanation. $\endgroup$ – Peregrine Rook Dec 28 '17 at 18:58
2
$\begingroup$

If we consider the new born option (the fact that 0 is divisible by any number :) ) I would add this [0,6,10,12,15] to (0,0,0,0,43).

But the only solution to this is the first one (6,6,6,10,15).

The way I found these solutions is by thinking in a brute force way and since the number of combinations is high, I wrote a program that took a minute or less to finish and gave me the desired output.

$\endgroup$
  • $\begingroup$ Bravo! I got the first two answers, and I missed this one.  But I don’t understand your second paragraph.  (Please do not respond in comments; edit your answer to make it clearer and more complete.)  And I’m tempted to downvote because you don’t list the numbers in numeric order. $\endgroup$ – Peregrine Rook Dec 28 '17 at 18:59
1
$\begingroup$

If all the ages are different, here is one solution.

0, 6, 10, 12, 15

$\endgroup$
  • $\begingroup$ This is the same as Rihab’s answer.   But +1 for listing the numbers in numeric order, and using spoiler markdown. $\endgroup$ – Peregrine Rook Dec 28 '17 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.