Cheque Denomination Optimization

Let $x, y, z$ be the number of ₹100, ₹250, and ₹500 cheques respectively. $x + y + z = 100 \quad \text{--- (1)}$ $100x + 250y + 500z = 15250 \implies 2x + 5y + 10z = 305 \quad \text{--- (2)}$

Multiply (1) by 2: $2x + 2y + 2z = 200$ Subtract from (2): $3y + 8z = 105$

We want to maximize $z$. $8z = 105 - 3y = 3(35 - y)$ Since $8z$ is divisible by 3 and $\gcd(8,3)=1$, $z$ must be a multiple of 3.

Also, $8z \le 105 \implies z \le 13.125$. Multiples of 3 less than 13: $z = 12, 9, 6, 3, 0$.

For $z = 12$: $8(12) = 96 \implies 3y = 105 - 96 = 9 \implies y = 3$ $x = 100 - 3 - 12 = 85$ Since $x, y, z \ge 0$, $z = 12$ is valid.

Maximum possible number of ₹500 cheques is 12.