About 2 min read

Two Simple Math Puzzles: Prime Numbers and Shortest Path

Here are two math puzzles, solve, comment and enjoy the discussion!

Puzzle 1: Prime Numbers

Prove that p21p^2-1 is divisible by 24, where pp is a prime number with p>3p>3.

This is a simple one - do not go by the technicality of the problem statement.

Solution 1

p21=(p1)×(p+1)p^2-1 = (p-1)\times (p+1) Given, pp is a prime number >3>3, p1p-1 and p+1p+1 are even. We can also write,

p1=2K,and p+1=2K+2=2(K+1)\begin{aligned} p-1=2K, \text{and } \cr p+1=2K+2=2(K+1) \end{aligned}

Given, KNK \in \mathbb{N}, either KK or K+1K+1 are also even. Hence, (p1)×(p+1)(p-1)\times (p+1) is divisible by 2×4=82\times 4 = 8.

Furthermore, as pp is prime, we can write it as either p=3s+1p = 3s+1 or p=3s1p = 3s-1, where sNs \in \mathbb{N}. In either case, one of p1p-1 or p+1p+1 are divisible by 3 as well.

Hence, p21p^2-1 is divisible by 8×3=248\times 3 = 24.

Puzzle 2: Hopping on a Chess Board

On a chess board, basically a 8×88\times 8 grid, how many ways one can go from the left most bottom corner to the right most upper corner? In chess naming conventions, from a1a1 to h8h8.

In the original post this problem was ill defined.

Please solve this problem with the constraints that only up and right moves are allowed.

Can you find the generic answer for the case of N×MN\times M grid?

Solution 2


For an N×MN\times M grid, we need only N1N-1 right and M1M-1 up moves.

Thank you Devin for pointing this out.

Given only forward moves are allowed, for any arbitrary grid of N×MN\times M, a total of (N1)+(M1)(N-1) + (M-1) moves are needed.

Any N1N-1 of these moves can be of type right and M1M-1 of type up. In short, this is a combinatorial problem of distributing N+M2N+M-2 objects into groups of N1N-1 and M1M-1. This is simply,

(N+M2N1)=(N+M2)!(N1)!(M1)!\dbinom{N+M-2}{N-1} = \frac{(N+M-2)!}{(N-1)! (M-1)!}

In the particular case of the chess board, N=M=8N = M = 8. Hence, total number of possible paths are:

No. of Paths=14!7!7!=3432\text{No. of Paths} = \frac{14!}{7! 7!} = 3432

Thank you Rohit and Amber for posting quick solutions!

Let me know if you have any other interesting alternative solutions to these problems.


RELATED POSTS | Algorithms

Get in touch 👋

Feel free to email me about anything. Want some advice? Give some feedback?

You can also reach me around the web: GitHub, Twitter, LinkedIn