1

One holiday, I gave each of my 3 grandsons x coins and each of my 4 granddaughters y coins. The total number of coins that I gave to my grandchildren will allow for only one ordered pair of positive intergers (x,y). At most how many coins did I give to my 7 grandchildren?

For the above question, or in general for any number of "a" grandsons, and "b" grand daughters, the total number of coins that satisfy the above requirements is given by the following formula: Total number of coins = 2 * (lowest common denominator of "a" and "b")

In the above case, total number of coins = 2 * 12 = 24. 12 is the lowest common denominator of 3 and 4.

My question is, how to prove that the above formula is correct...?

-Peter

Peter Chander
  • 11

1 Answers1

0

The total number of coins $N$ is fixed as $N=3a+4b$ if we also have a second expression $N=3c+4d$ we subtract and find $3(a-c)=4(d-b)$.

Since $3$ and $4$ are coprime (if they are not, identfy and extract their highest common factor at this stage), we must have $4|a-c$ so that $a-c=4e$, whence $d-b=3e$ - with $e$ an integer. We therefore have $c=a-4e$ and $d=b+3e$.

Now it is clear that if we define $c$ and $d$ by those equations, then $N=3c+4d$ whatever we choose for $a$. And the constraint is that no non-zero integer choice of $e$ will leave both $c$ and $d$ positive. This means for $e=1$ that $a\leq 4$, and for $e=-1$ (to throw the focus on $b$) we have $b\leq 3$. If any positive(negative) $e$ gives a second solution for $N$, it is easy to see that $e=1(-1)$ also solves for $N$.

Plugging these into the original equation we have $N\leq 12+12=24$.

Doing the extraction of the highest common factor at the point indicated, leads rapidly to the correct solution for cases where the numbers of grandsons and granddaughters have a common factor.

Mark Bennet
  • 100,194