Here's a third puzzle that I found in a book, slightly paraphrased because I don't entirely remember the format of the original.

A medical researcher is trying to test the effect of a certain drug on mice. He is supposed to collect data for all doses from 1 to 50 units, but only has the data collection resources for 25 tests. He has decided to only test dose amounts that are not multiples or factors of each other (for example, if he decided to use a dose of 15 units for a specific test, that would preclude tests for 1, 3, 5, 30, or 45 units). Moreover, because the drug is relatively expensive, he wants to use as little of the drug as he can manage to run these tests.

How can he arrange the dosage amounts so that he ends up using all 25 test packages, and the total units of dosage used in the tests are as low as possible?

The book had the answer, but one, it didn't explain how the answer was arrived at, and two, I don't remember what the answer was and no longer have that book with me.

  • $\begingroup$ Am I missing something, or is the goal just to find 25 coprime numbers from 25 to 50? $\endgroup$ – Aza May 20 '14 at 4:33
  • $\begingroup$ They don't have to be coprime. There just can't be any two where one is a factor of the other. And the range is from 1 to 50, not 25 to 50. $\endgroup$ – Joe Z. May 20 '14 at 4:34
  • $\begingroup$ Wouldn't a single test of 1 unit technically satisfy the requirement? Or am I missing something? Ah, I guess you have to perform exactly 25 tests. $\endgroup$ – arshajii May 20 '14 at 14:28
  • $\begingroup$ Yea. Wouldn't 1 win? $\endgroup$ – awesomepi May 20 '14 at 19:24
  • $\begingroup$ You have to use all 25 tests. $\endgroup$ – Joe Z. May 20 '14 at 19:31

By logically starting from 26-50 and trying to shrink them one by one you can easily show: $8,12,14,17,18,19,20,21,22,23,25,26,27,29,30,31,33,35,37,39,41,43,45,47,49$

Which equals $711$

This is performed by replacing every even number by itself divided by two if and only if the result is not a divisor of any other number (usually if that number times $3$ remains) from $50$ to the lowest number. Then you repeat this process until you get the answer above.

I am not convinced that this is definitely the smallest and am therefore worked on an alternative solution but this answer was also MY programming result so I a confident enough to include it as an answer.

  • $\begingroup$ @Travis J 16 is covered exactly as thoroughly as 50, 32 or other numbers. What do you mean by your comment? $\endgroup$ – kaine May 21 '14 at 18:18
  • $\begingroup$ @kaine He meant he didn't see a number in the list that was either a multiple or factor of 16, but 8 is in that list. $\endgroup$ – Joe Z. May 21 '14 at 18:31
  • $\begingroup$ This improves on mine by replacing $16,24$ with $8,12$. Good work. $\endgroup$ – Ross Millikan May 21 '14 at 19:35
  • $\begingroup$ @RossMillikan agreed, I believe it uses the same strategy as you used to get your answer and then just repeated the strategy. Unfortunately, it doesn't get any smaller easily. $\endgroup$ – kaine May 21 '14 at 19:36
  • $\begingroup$ FYI, i've used a more advanced program which iterated through every combination of numbers with no cofactor less than 50 where at least one is less than 9. This program indicated that the above solution was the smallest. The only way for one to be smaller is if there is another series starting with a number greater than 8 or I made a mistake. $\endgroup$ – kaine May 23 '14 at 18:17

The best I can get by hand is $14,16,17,18,19,20,21,22,23,24,25,26,27,29,30,31,33,35,37,39,41,43,45,47,49$ for a sum of $731\ $. I started with $26$ through $50$, then replaced big numbers by small numbers wherever I could.

  • $\begingroup$ I've put this question on PCG.SE - hopefully we'll get a computer-generated answer that does a little better. $\endgroup$ – Joe Z. May 21 '14 at 0:10

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.