1
$\begingroup$

Let an equilateral triangle have the length of each side an integer $N$. I need to find if it is possible to transform the triangle keeping two sides fixed and alter the third side such that it still remains a triangle, but the altered side will have its length as an even integer, and the line drawn from the opposite vertex to the mid-point of the altered side is of integral length, i.e. it becomes an isosceles triangle.

Example : If $N=5$ then the answer is YES while if $N=3$ answer is NO.

It's a computer graphics problem that is a sub-part of bigger problem, I have been racking brains about maths and the concept behind it, to solve my problem.

$\endgroup$
  • $\begingroup$ Suppose that $a$ is half the altered side, and $b$ is the distance from the vertex to the midpoint of the altered side. By the Pythagorean Theorem we want $a^2+b^2=N^2$. This has a non-trivial solution precisely if $N$ is divisible by a prime of the form $4k+1$. (I am making this a comment since I think I have seen this question on MSE recently.) $\endgroup$ – André Nicolas Oct 3 '15 at 16:17
  • $\begingroup$ @AndréNicolas: Programatically how to check it? Any logic? $\endgroup$ – cold_coder Oct 3 '15 at 18:40
  • $\begingroup$ I don't know what you mean by programmatically. With a program? We can find the prime factorization of $N$, and see whether among the prime factors there is a prime of the shape $4k+1$. But factoring huge numbers appears to be computationally difficult. $\endgroup$ – André Nicolas Oct 3 '15 at 20:56
1
$\begingroup$

To restate your question more clearly, you are asking what kind of integer number $N$ can be the hypothenuse of a right-angled triangle, so that the other two sides are of integer length too.

The answer is well known: $N$ must be (the multiple of) the sum of two perfect squares: $N=a^2+b^2$ (or $N=k(a^2+b^2)$). If so, the other two sides (which in your problem are half the modified side and "the line drawn from the opposite vertex to the mid-point of the altered side") are given by $a^2-b^2$ and $2ab$ (multiplied by $k$ if needed).

Example: $5=2^2+1^2$, $3=2^2-1^2$, $4=2\cdot(2\cdot1)$.

$\endgroup$
  • $\begingroup$ Then how to check that it is multiple of square of two numbers or not? $\endgroup$ – cold_coder Oct 3 '15 at 18:39
  • $\begingroup$ But how to calculate a and b, as stated in your answer.... ??? $\endgroup$ – Lauren Oct 3 '15 at 19:53
  • $\begingroup$ @cold_coder André Nicolas gave the answer in his comment: you must check that all prime factors of $N$ be of the form $4k+1$. $\endgroup$ – Aretino Oct 3 '15 at 20:01
  • $\begingroup$ Ok got it! Thank you! $\endgroup$ – cold_coder Oct 3 '15 at 20:03
  • $\begingroup$ @cold_coder I forgot to mention that is is valid for primitive triples: in general $N$ can be a product of prime factors of the form $4k+1$ times any positive integer number. In practice, only those numbers which don't have any prime factor of the form $4k+1$ must be discarded. $\endgroup$ – Aretino Oct 3 '15 at 20:09
1
$\begingroup$

This is a question from CodeChef October Challange. Please dude dont lie

$\endgroup$

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.