Algebra question
Discussion
The radio 4 puzzle for last Friday was easy enough through trial and error, but I can't understand the algebraic way of doing it.
https://www.bbc.co.uk/programmes/articles/3MB6TpfS...
https://www.bbc.co.uk/programmes/articles/3MB6TpfS...
puzzle answer said:
The annual fees for the Puzzle Challenge Club are £23 per person, with a special rate for senior citizens of £17. If the total amount of dues collected last year was £1500, what is the smallest number of senior citizens that belong to the club?
Today’s #PuzzleForToday has been set by Dr Steve Humble from Newcastle University
Click here for the answer
There are only 4 possible alternative ways of the club fees being £1500. The alternative with 3 senior citizens is the smallest.
Details of a possible solution.
23X +17Y = 1000
We can re-write this equation as
X = 12 – 17n and Y = 72 + 23n
where n can take values of 0, -1, -2, -3
Q Y senior X general Senior fees General fees
0 72 12 £1224 £276
-1 49 29 £833 £667
-2 26 46 £442 £1058
-3 3 63 £51 £1449
Where does the 1000 come from in the first equation? Or the 12 and the 72 in the next two?Today’s #PuzzleForToday has been set by Dr Steve Humble from Newcastle University
Click here for the answer
There are only 4 possible alternative ways of the club fees being £1500. The alternative with 3 senior citizens is the smallest.
Details of a possible solution.
23X +17Y = 1000
We can re-write this equation as
X = 12 – 17n and Y = 72 + 23n
where n can take values of 0, -1, -2, -3
Q Y senior X general Senior fees General fees
0 72 12 £1224 £276
-1 49 29 £833 £667
-2 26 46 £442 £1058
-3 3 63 £51 £1449
I don't understand the solution as presented but it's a linear equation to minimise y and y must be greater than 0
So try y=1 and you get 64.4 full paying members which is obviously incorrect. Try y=2 and you get 63.73 ditto. Try y= 3 and you have a minimum solution of 63.
I am sure that someone can do a better job than me of explaining the rest. I could even be wrong too. It happens quite often according to my wife!
So try y=1 and you get 64.4 full paying members which is obviously incorrect. Try y=2 and you get 63.73 ditto. Try y= 3 and you have a minimum solution of 63.
I am sure that someone can do a better job than me of explaining the rest. I could even be wrong too. It happens quite often according to my wife!
The 1000 appears to have been a typo as it now says 1500 (it definitely said 1000 when I looked at it this morning.
Clearly my engineering degree was too long ago for me to remember what the next bit is about though, so I passed it on to my wife who teaches A-Level maths and she couldn't remember how to do it either but is going to work it out and explain it to me later
Clearly my engineering degree was too long ago for me to remember what the next bit is about though, so I passed it on to my wife who teaches A-Level maths and she couldn't remember how to do it either but is going to work it out and explain it to me later
23j + 17 k = 1500, make k as small as possible and j large, with both +ve integers
You could do a sequential search, k = 1, 2 ....
or you could use a bit of insight/intuition to narrow down the range of possibilities for the number of seniors:
substitute m = j - k to obtain
k = 50 - 23*(m/30), make k small as small as possible and (m/30) large, with both k and (m/30) +ve integers
At that point, the range of possible k is very small and the answer is obvious
You could do a sequential search, k = 1, 2 ....
or you could use a bit of insight/intuition to narrow down the range of possibilities for the number of seniors:
substitute m = j - k to obtain
k = 50 - 23*(m/30), make k small as small as possible and (m/30) large, with both k and (m/30) +ve integers
At that point, the range of possible k is very small and the answer is obvious
Another way to look at it could be to take £1500 and divide by 23 = 65.2,
So, if there were 65 normal members, this would give a total taking of 65x23 = £1495,
65 members leaves £5 short, which is not divisible by £17 (membership for OAP)
If you then reduce the normal members by 1, to 64, the remainder is £5 + £23 = £28 (which is also not divisible by £17).
Further reducing normal members to 63 leaves a remainder of £5 + £23 + £23 = £51 (which IS divisible by £17 - 3 times) so 3 OAPs is smallest number.
So, if there were 65 normal members, this would give a total taking of 65x23 = £1495,
65 members leaves £5 short, which is not divisible by £17 (membership for OAP)
If you then reduce the normal members by 1, to 64, the remainder is £5 + £23 = £28 (which is also not divisible by £17).
Further reducing normal members to 63 leaves a remainder of £5 + £23 + £23 = £51 (which IS divisible by £17 - 3 times) so 3 OAPs is smallest number.
[quote=C&C] Another way to look at it could be to take £1500 and divide by 23 = 65.2,
So, if there were 65 normal members, this would give a total taking of 65x23 = £1495,
65 members leaves £5 short, which is not divisible by £17 (membership for OAP)
If you then reduce the normal members by 1, to 64, the remainder is £5 + £23 = £28 (which is also not divisible by £17).
Further reducing normal members to 63 leaves a remainder of £5 + £23 + £23 = £51 (which IS divisible by £17 - 3 times) so 3 OAPs is smallest number.
[/quote]
The OP said it was easy to solve with trial & error, which it is. He was looking for an algebraic solution.
So, if there were 65 normal members, this would give a total taking of 65x23 = £1495,
65 members leaves £5 short, which is not divisible by £17 (membership for OAP)
If you then reduce the normal members by 1, to 64, the remainder is £5 + £23 = £28 (which is also not divisible by £17).
Further reducing normal members to 63 leaves a remainder of £5 + £23 + £23 = £51 (which IS divisible by £17 - 3 times) so 3 OAPs is smallest number.
[/quote]
The OP said it was easy to solve with trial & error, which it is. He was looking for an algebraic solution.
Edited by TwigtheWonderkid on Saturday 20th June 21:10
We start with the following equation:
23x + 17y = 1500, where x and y are both elements of the positive integers.
The trick here is to try to rewrite the equation in some form which allows a reduction in the range which needs to be checked. We find a substitution which has a nice sized common divisor with 1500.
We substitute m = x - y which gives the following equation:
23m + 40y = 1500.
The greatest common denominator of 1500 and 400 is 20. In other words, 40y is a multiple of 20, 1500 is a multiple of 20, and therefore 23m must be a multiple of 20.
23 and 20 are co-prime (23 is in fact prime), therefore we define m = 20n.
Substitute and simplify:
23n + 2y = 75.
We can now test some possible solutions.
To start, we can set n = Floor 75/23 = 3.
23 n = 69
Therefore try 2y = 75-69 = 6, and therefore y =3 is a possible solution.
However, we have not proved that y=3 is the lowest solution. However, it does mean that we only have 3 other solutions (y=0..2) to test.
We now test y=0; No solution; y=1; No integer solution; y=2; No integer solution.
Therefore the lowest value of y = 3.
23x + 17y = 1500, where x and y are both elements of the positive integers.
The trick here is to try to rewrite the equation in some form which allows a reduction in the range which needs to be checked. We find a substitution which has a nice sized common divisor with 1500.
We substitute m = x - y which gives the following equation:
23m + 40y = 1500.
The greatest common denominator of 1500 and 400 is 20. In other words, 40y is a multiple of 20, 1500 is a multiple of 20, and therefore 23m must be a multiple of 20.
23 and 20 are co-prime (23 is in fact prime), therefore we define m = 20n.
Substitute and simplify:
23n + 2y = 75.
We can now test some possible solutions.
To start, we can set n = Floor 75/23 = 3.
23 n = 69
Therefore try 2y = 75-69 = 6, and therefore y =3 is a possible solution.
However, we have not proved that y=3 is the lowest solution. However, it does mean that we only have 3 other solutions (y=0..2) to test.
We now test y=0; No solution; y=1; No integer solution; y=2; No integer solution.
Therefore the lowest value of y = 3.
Congratulations to everyone who actually solved the problem. That’s all apart from me who didn’t solve it due to an embarrassing error in my arithmetic.
The best way to solve the problem is a systematic, numerical search. It’s general, not too slow by hand if you put some insight into the starting value, and very fast by computer. If you had work by hand, you might make a plot to speed up the process. However, the OP wanted an algebraic solution. That implies that it has to be done without searching through numbers.
WatchfulEye reached a solution without a search. It might appear that the method still resorts to a search at the very end to demonstrate that the solution for the number of seniors is a minimum. In fact, that’s not necessary. The solution depends on dividing two integers, knowing the result has to be another integer. In Watchful’s algebra, the result of the division is the Floor integer plus the Remainder. The whole problem is resolved by setting the remainder to zero. Since the Floor is by definition the larges possible value of the quantity m, the subsequent search is unnecessary. WatchdulEye’s solution is completely algebraic.
To make that all clearer, I’ll work through it again in my (engineer’s) terms. We have the equation
23j + 17k = 1500 - find the smallest k, largest j combination where k, j are both integers
To make the numbers rounder and smaller substitute
m = j – k so we’re no solving
23m + 40k = 1500 - find the smallest k, largest m combination where k, m are both integers
Rearrange the equation in a series of steps noting that at each step all terms in the equation remain integer to reach
m/20 = (75 – 2k)/23
Do the division on the right-hand side
m/20 = 3 + (6 – 2k)/23
where the integer 3 is the Floor – the biggest possible value of m given it’s an integer and that the remainder can be made to equal zero. Since that gives the biggest m, whatever we find for k must be the smallest.
The remainder equals zero when k = 3
So the solution is k = 3, m = 60, j = 63
I give all credit to WatchfulEye
Watchful’s method works very neatly for this case as the numbers can be made to turn out nicely, mainly thanks to the substitution m = j - k. If you change the values in the first equation, the method may need a couple of extra steps.
The best way to solve the problem is a systematic, numerical search. It’s general, not too slow by hand if you put some insight into the starting value, and very fast by computer. If you had work by hand, you might make a plot to speed up the process. However, the OP wanted an algebraic solution. That implies that it has to be done without searching through numbers.
WatchfulEye reached a solution without a search. It might appear that the method still resorts to a search at the very end to demonstrate that the solution for the number of seniors is a minimum. In fact, that’s not necessary. The solution depends on dividing two integers, knowing the result has to be another integer. In Watchful’s algebra, the result of the division is the Floor integer plus the Remainder. The whole problem is resolved by setting the remainder to zero. Since the Floor is by definition the larges possible value of the quantity m, the subsequent search is unnecessary. WatchdulEye’s solution is completely algebraic.
To make that all clearer, I’ll work through it again in my (engineer’s) terms. We have the equation
23j + 17k = 1500 - find the smallest k, largest j combination where k, j are both integers
To make the numbers rounder and smaller substitute
m = j – k so we’re no solving
23m + 40k = 1500 - find the smallest k, largest m combination where k, m are both integers
Rearrange the equation in a series of steps noting that at each step all terms in the equation remain integer to reach
m/20 = (75 – 2k)/23
Do the division on the right-hand side
m/20 = 3 + (6 – 2k)/23
where the integer 3 is the Floor – the biggest possible value of m given it’s an integer and that the remainder can be made to equal zero. Since that gives the biggest m, whatever we find for k must be the smallest.
The remainder equals zero when k = 3
So the solution is k = 3, m = 60, j = 63
I give all credit to WatchfulEye
Watchful’s method works very neatly for this case as the numbers can be made to turn out nicely, mainly thanks to the substitution m = j - k. If you change the values in the first equation, the method may need a couple of extra steps.
Thanks Peter. I'd missed the part about the remainder being the smallest possible solution.
If you can recognise this as a linear diophantine equation, then you can use specific solution methods - these typically have roots based on greatest common divisor or the Chinese reminader theorem.
If you can recognise this as a linear diophantine equation, then you can use specific solution methods - these typically have roots based on greatest common divisor or the Chinese reminader theorem.
Gassing Station | Science! | Top of Page | What's New | My Stuff