A number theory problem by Dinesh Nath Goswami
If 2 9 x + 3 0 y + 3 1 z = 3 6 6 , where x , y and z are non-negative integers , then find the least value of x + y + z .
The answer is 12.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
6 solutions
Nice observation but that doesn't prove that it is minimum
Great observation, but note that non-leap years only have 365 days, so what we're dealing with here is a leap year, in which February has 29 days instead of the "usual" 28. The solution triple ( x , y , z ) = ( 1 , 4 , 7 ) corresponds to your interpretation, but note that there are other solution triples. What they all have in common, though, is that x + y + z = 1 2 .
Great Observation
Firstly I'm going to assume you mean positive or at least non-negative integral value otherwise there is more than one answer (try x = 2 0 , y = − 3 , z = − 4 ⟹ x + y + z = 1 3 ).
Clearly we have 0 ≤ x , y , z < 1 3 otherwise the expression will be too large (as all variables are positive).
Consider the expression ( m o d 2 9 ) :
2 9 x + 3 0 y + 3 1 z ≡ y + 2 z ≡ 1 8 ( m o d 2 9 ) As 3 6 6 ≡ 1 8 ( m o d 2 9 )
Note 0 ≤ y , z < 1 3 ⟹ 0 ≤ y + 2 z < 3 9 . Combining this with the above expression we get y + 2 z = 1 8 :
2 9 x + 3 0 y + 3 1 z = 2 9 ( x + y + z ) + ( y + 2 z ) = 2 9 ( x + y + z ) + 1 8
2 9 x + 3 0 y + 3 1 z = 3 6 6 ⟹ 2 9 ( x + y + z ) + 1 8 = 3 6 6 ⟹ x + y + z = 2 9 3 4 8 = 1 2
The reasons we need the non-negative condition is because otherwise y + 2 z ≡ 1 8 ( m o d 2 9 ) has infinite solutions (e.g. 1 8 , 4 7 , − 1 1 ).
Set ( x , y , z ) = ( 3 0 k − 3 6 5 , 3 6 4 − 2 9 k , 1 ) . This gives:
{ 2 9 x + 3 0 y + 3 1 z = 2 9 ( 3 0 k − 3 6 5 ) + 3 0 ( 3 6 4 − 2 9 k ) + 3 1 x + y + z = ( 3 0 k − 3 6 5 ) + ( 3 6 4 − 2 9 k ) + ( 1 ) = 3 6 6 = k
Thus we could generate any value for x + y + z .
Moderator note:
Finding the seed solution is often the hardest part of solving the linear diophantine equation.
It generally helps if we can restrict the values somehow, especially by considering modulo the coefficients.
I've edited the problem to specify that x , y , z must be non-negative in order to achieve a unique solution. The possible triples are then ( x , y , z ) = ( 0 , 6 , 6 ) , ( 1 , 4 , 7 ) , ( 2 , 2 , 8 ) and ( 3 , 0 , 9 ) , all of which yield that x + y + z = 1 2 . Nice solution, btw. :)
Good idea to use modular arithmetic and also , for reflection , a good illustration of understanding and expressing the auto-referentiality in terms of this arithmetic anyway.
In general it's use is very cute in any quantitative problem where some equation/expression is determined by operations that are reducible to and can be thought by a continuously repeating constant like here as it makes direct exactly that so to say repetitive by a constant increase of quantity given anyway.
29x + 30y + 31z = 366
Can be written as
30(x + y + z) = 366 + x - z.
RHS has to be multiple of 30 and 360 is the number closest to the RHS that keeps x and z as small as possible.
Hence x + y + z from the LHS can be equated to 12
The first thought that came to me was that 366 were the no. of days in a leap year with months having days 29 , 30 , 31
There are 12 months in a calendar year
So the answer is 12
Writing 29 as 30 - 1, And 31 as 30 + 1, it's Easy To See that 12 Times 30 is The cheapest Way to reach something near 366. Now, Just put z = x + 6. A value x + y + z < 12 won't neither reach 366 (z = 11 --> 341)
Use AM-GM inequality. (value is slight greater than 12 but since we need an integer value 12 is the answer
Notice that the coefficients of x, y and z are the number of days of the different kinds of month we have. Also, 366 is the number of days there are in a year. From there it follows, that the sum of x, y and z must be 12, because we have 12 months a year.