0

I have two equations of the form :

$ax + by + cz = k$ and $x + y + z = n$

I need to find the number of solutions of these equations. Here $a, b, c, k$ can range from $10^{-9}$ to $10^9$ and $n$ ranges from $1$ to $10^5$.

Actually the original problem was something else but I kind of boiled it down till here. No idea if this is even feasible to calculate, just giving it a shot here. I know the usual dynamic programming based solution can solve it but the constraints won't actually allow to use such a approach. Thus I thought of maybe finding a mathematical answer to it.

Also, there's just one more catch here, a solution will be different for different choice of variable. Don't really know how to state this but for example, suppose an answer is $(1, 1, 1)$, then which $1$ is assigned to which variable also matters. So here this will actually count as three different answers.

To say again, don't really know if it is feasible to even solve, but if someone has some trick or some kind of answer to it, I'd really appreciate it.

resound
  • 128
  • Unless you have $a=b=c=1$ and $k\not=n,$ you will have infinitely many solutions, because the system is underdetermined. – Adrian Keister Jun 27 '19 at 18:29
  • 1
    @AdrianKeister That’s not the only possibility for an inconsistent system. – amd Jun 27 '19 at 18:31
  • It is up to an equivalence class of multiplying the equation by a constant, which is essentially saying the same thing as your answer. – Adrian Keister Jun 27 '19 at 18:38

3 Answers3

1

The two equations describe (presumably distinct) planes. The planes are parallel if the vectors normal to them are parallel. This occurs if the ratios of the coefficients are the same: $$a:b:c=1:1:1$$ In other words, if $a=b=c$, there is no solution, assuming the planes are distinct. If the planes are not distinct, then $k=an$ and there are an infinite number of solutions. But if this is the case, both of your equations would be identical (up to a constant factor).

Otherwise, the two planes intersect an infinite number of times along a line.

Andrew Paul
  • 732
  • 1
    Not quite. When $a=b=c$, the system is consistent if $k=an$. The two planes coincide. – amd Jun 27 '19 at 18:35
  • I assumed that the equations described distinct planes in the beginning. I'll make that a little more clear. – Andrew Paul Jun 27 '19 at 18:37
  • Hmm maybe I'm unable to generate a proper condition. Is there some extra condition that maybe applied to restrict the solutions? Like a bound on something maybe? @mathysics – resound Jun 27 '19 at 18:41
  • That depends on the parameters of your problem. For example, if there is another linear equation relating $x$, $y$, and $z$, then there could be just one unique solution. But given just two linear equations, all we can conclude is that there is either no solution or infinite solutions. – Andrew Paul Jun 27 '19 at 18:44
  • @mathysics Well my original problem said: Find number of paths from Y to Z that take n steps, and in one step I can move from any position i to i+a or i+b or i+c. Constraints remain the same. Due to large constraints I cannot do it by recursion simply, any suggestions? – resound Jun 27 '19 at 19:10
  • Ah so these are diophantine equations. That is, $x,y,z,n\in\mathbb{N}$. Those can be solved with fairly standard techniques. See here @sh1ve9. – Andrew Paul Jun 27 '19 at 19:20
  • @mathysics So will it give me all the solutions, even for the last catch that I stated in the OP. Also, what about the big constraints? – resound Jun 27 '19 at 19:26
  • 1
    @sh1ve9 it should give you all solutions. If you get the solution $(1,1,1)$, that means you take one step of each of size $a,b,c$. The number of ways these steps can be ordered is $3!=6$. If you had the solution (1,2,3), then there are $6$ steps in total which can be ordered in $\frac{6!}{1!2!3!}=60$ different distinct ways. In general, for a solution $(r,s,t)$, the number of distinct paths from that triple is: $$\frac{(r+s+t)!}{r!s!t!}.$$ – Andrew Paul Jun 27 '19 at 20:24
  • @mathysics Wow that was just what I needed. Thank you! :) – resound Jun 27 '19 at 20:26
  • Let us continue this discussion in chat. – resound Jun 28 '19 at 14:46
0

The system is underdetermined, so it has either no solution or an infinite number of them. There is no solution when $a=b=c$ but $k\ne an$.

amd
  • 53,693
  • Hmm maybe I'm unable to generate a proper condition. Is there some extra condition that maybe applied to restrict the solutions? Like a bound on something maybe? @amd – resound Jun 27 '19 at 18:34
0

You should be ashamed for successfully cheating in ongoing Hackerearth June Coding Circuits.

Firex Firexo
  • 295