How to prove the following expression

188 Views Asked by At

Prove that if it takes you 5 minutes to solve any Sudoku puzzle and 14 minutes to solve a word search, you can completely occupy yourself on any flight of 52 minutes or longer provided that you have a puzzle book with enough puzzles.

I thought that proving this expression would require creating a linear equation to represent the conditions: 5x + 14y >= 52 And then you could show that given any x's or y's such that there are enough x's and y's to let the equation be true then the expression is true.

What I don't understand is how to go about proving this or rather why? It seems to me that the proof already mentions that there are sufficient x and y such that the expression holds meaning that the proof question already has proven the answer.

2

There are 2 best solutions below

0
On BEST ANSWER

First note that you can make 52, 53, 54, 55 and 56: $$\begin{aligned} 2\cdot 5+3\cdot 14=52,\\ 5\cdot 5+2\cdot 14=53,\\ 8\cdot 5+1\cdot 14=54,\\ 11\cdot 5+0\cdot 14=55,\\ 0\cdot 5+4\cdot 14=56. \end{aligned}$$ Now let $n\geq 57$ be an integer. If the last digit of $n$ is $0$, $1$, $7$, $8$ or $9$, then subtract $5$ once. After that we can repeatedly subtract $2\cdot 5=10$, until $52\leq n-5p\leq 56$, where $p$ is the amount of times we subtracted $5$. Then $n=5\cdot p + q$, where $q\in\{52,53,54,55,56\}$. Therefore, we can write $n=x\cdot 5+y\cdot 14$ for some integers $x,y$ for all $n\geq 52$.

1
On

This result is known as the Chicken McNugget theorem. (There is a proof in the link.)