
Elementary Math Fractions, Percentages, Word Problems, Equations, Inequations, Factorization, Expansion 
 LinkBack  Thread Tools  Display Modes 
June 4th, 2018, 10:05 AM  #1 
Newbie Joined: Feb 2018 From: California Posts: 17 Thanks: 1  Multiple Multiples
Hello, Pretend I wanted to buy magic pencils. There's only one store that sells them and they are sold in packages of 6, 9, and 15. What is the most straightforward way to figure out if I can buy X number of magic pencils? For example, if I want to buy 4,238 pencils, would that be possible using only the multiples of 6, 9, and 15? What about 88,904 magic pencils? What's the generic way to go about solving this problem? I am most interested in solving this using only elementary school level math. 
June 4th, 2018, 10:14 AM  #2 
Senior Member Joined: Sep 2015 From: USA Posts: 2,042 Thanks: 1064 
Problems like this are known as linear diophantine equations and are a well studied branch of number theory. Number theory isn't really my thing but it appears there are well known methods for solving systems of these equations. Elementary school level math it's not, but the individual steps of the algorithm look straightforward enough. I'd start here. 
June 4th, 2018, 11:01 AM  #3  
Senior Member Joined: Aug 2012 Posts: 1,973 Thanks: 551  Quote:
https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem  
June 4th, 2018, 12:28 PM  #4 
Senior Member Joined: Sep 2015 From: USA Posts: 2,042 Thanks: 1064  
June 4th, 2018, 12:57 PM  #5  
Senior Member Joined: Feb 2010 Posts: 683 Thanks: 129  Quote:
I think you may have meant 6, 9, and 20 (not 15). If that is the case then you may want to google "chicken mcnuggets problem". I don't think there is a general procedure to solve these but here is a heuristic that might help. Make a table with six columns: 1 2 3 4 5 [6] 7 8 [9] 10 11 12 13 14 15 16 17 18 19 [20] 21 22 23 24 25 26 27 28 [29] 30 31 32 33 34 35 36 37 38 39 [40] 41 42 43 44 45 46 47 48 [49] 50 51 52 53 54 Every time you find a solution, put it in brackets. As soon as you find a solution in each column, you have a potential solution to the problem. For 6, 9, and 20, I have found solutions 6 = 6+0+0, 9 = 0+9+0, 20 = 0+0+20, 29 = 0+9+20, 40 = 0+0+20+20, and 49 = 0+9+20+20. Any number below a solution is obtainable. So in this case (6,9,20) any number greater than 43 can be purchased. Last edited by skipjack; June 5th, 2018 at 07:02 PM.  
June 5th, 2018, 02:23 PM  #6 
Newbie Joined: Feb 2018 From: California Posts: 17 Thanks: 1 
OK, thank you. I like your heuristic, mrtwhs.


Tags 
multiple, multiples 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to find the sum of the multiples  popoder  Algebra  5  March 6th, 2016 05:20 AM 
prove that $x$ and $y$ are multiples  walter r  Linear Algebra  1  July 29th, 2014 01:15 PM 
multiples  nitin1  Number Theory  11  December 14th, 2012 09:59 AM 
converting multiples  Tylerman  Applied Math  4  January 30th, 2012 01:15 PM 
multiples of 2 pi  Icevox  Number Theory  8  March 25th, 2011 01:11 PM 