0

I was recently using this program that I made for a question I was asked.

It goes as follows,

"Kevin and Devin each make one hat per day for charity, but they started on different days. Today, Kevin made his 520th hat, and Devin made his 50th. A celebration is planned for the next day that Kevin’s hat count is evenly divisible by Devin’s hat count. In how many days from today will they celebrate?"

I made it so that my code could work for any number of hats Kevin and Devin start with. My code only checks for the first 1000 days, so the program does not go on forever.

I was wondering, is there a way to check if Kevin and Devin will ever celebrate, given to numbers to start with?

IAmBlake
  • 255
nedla2004
  • 101

1 Answers1

0

At the very least you can reduce the problem to testing a finite set of values.

Let $k$ and $d$ be the initial hat counts for Kevin and Devin, respectively. After $n$ days their hat counts are $k+n$ and $d+n$. Suppose that $k+n$ is a multiple of $d+n$, say $k+n=m(d+n)$; then

$$k-md=(m-1)n\;.$$

If $m=1$, $k=d$, and we can simply take $n=0$. Otherwise,

$$n=\frac{k-md}{m-1}\;,$$

and it’s clear that at worst we need only try values of $m$ satisfying $1<m\le\left\lfloor\frac{k}d\right\rfloor$, since $n$ cannot be negative.

A different bound can be obtained by noticing that no $n$ satisfying $\frac{k+n}{d+n}<2$ can be a solution, so we need only consider $n\le k-2d$. Thus, at worst we need test only

$$\min\left\{k-2d,\left\lfloor\frac{k}d\right\rfloor\right\}$$

possibilities.

Brian M. Scott
  • 616,228
  • For me, this does not seem to work. I am now using MAX = min(kevin-2*devin, int(kevin/devin)). Am I not understanding what you are saying, or is something else different? (For an example of a case that does not work, try 575 and 67) – nedla2004 Oct 08 '16 at 19:42
  • @nedla2004: It works fine: when you set $m=2$ in the first test, you find that $\frac{575-2\cdot67}{2-1}=441$ is an integer, and indeed $575+441=1016=2\cdot508=2\cdot(67+441)$, so $441$ days will do the trick. – Brian M. Scott Oct 08 '16 at 19:46