12
$\begingroup$

Fill in each blank unshaded cell in the diagram below with a positive integer less than 100, such that every consecutive group of unshaded cells within a row or column is an arithmetic sequence.

enter image description here

This problem is from the USAMTS Round 3 problem set.

$\endgroup$
  • $\begingroup$ The close voter did not assume that there is just one solution possible, this is nothing but broad :) @AlecDelgado can you edit the question to say this has an unique solution? $\endgroup$ – skv Dec 14 '14 at 18:51
  • 5
    $\begingroup$ Yes, I think it was an excellent puzzle. Problem being, there are excellent puzzle-solvers at work here as well! I stand no chance with their speed. But I think once everything is nicely spoiler-tagged away, this puzzle serves as an excellent example of a good mathematical puzzle! One thing though: Some people might be distracted by the term "arithmetic sequence" - even if they are otherwise good with numbers. Maybe give one example for convenience? $\endgroup$ – BmyGuest Dec 14 '14 at 18:54
  • 3
    $\begingroup$ I didn't know it was that easy to solve USAMTS Round 3 problems, just ask others on the internet! meta.math.stackexchange.com/q/18745/18398 $\endgroup$ – Joel Reyes Noche Dec 15 '14 at 5:16
  • 4
    $\begingroup$ This is (as Joel points out) a question in an active contest. There is now a meta discussion on how to handle these situations; as it has the lesser potential for harm, until the community has come to a decision one way or another I have applied the Mathematics policy and locked it, deleting answers. The answers will be restored and the question unlocked when the contest is over or a different consensus is reached on meta. $\endgroup$ – Kevin Dec 15 '14 at 5:58
  • 2
    $\begingroup$ As this competition has ended, the question has been unlocked and the answers restored. Thanks for your patience, guys! $\endgroup$ – Aza Jan 21 '15 at 10:08
17
$\begingroup$

TL;DR. The solution is:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&71&83&95&\\ &&13&18&&20&35&50&65&&&\\ 03&10&17&24&&22&&41&59&77&95&\\ 27&&&30&&24&&32&&&77&\\ 51&46&41&36&31&26&&23&35&47&59&\\ \end{array}$$

And I prove that no other solution exists.


Here is the proof:

Starting position:

$$\begin{array}{rrrrrrrrrrrl} 03&-&-&-&-&-&&59&-&-&-&\\ &&-&-&&-&-&-&-&&&\\ -&10&-&-&&-&&-&-&-&-&\\ -&&&-&&-&&-&&&-&\\ -&-&-&-&31&26&&-&-&-&59&\\ \end{array}$$

Filling from the $26$ and $31$:

$$\begin{array}{rrrrrrrrrrrl} 03&-&-&-&-&-&&59&-&-&-&\\ &&-&-&&-&-&-&-&&&\\ -&10&-&-&&-&&-&-&-&-&\\ -&&&-&&-&&-&&&-&\\ 51&46&41&36&31&26&&-&-&-&59&\\ \end{array}$$

First guess:

Guessing what should go up from the $51$, we should get decrements up to $25$. If we try decrementing by $26$ or higher, we will get a negative number left to the $10$.

Lets try decrementing by $20$:

$$\begin{array}{rrrrrrrrrrrl} 03&-&-&-&-&-&&59&-&-&-&\\ &&-&??&&-&-&-&-&&&\leftarrow \text{Can't put -06, can't be negative.}\\ 11&10&09&08&&-&&-&-&-&-&\\ 31&&&22&&-&&-&&&-&\\ 51&46&41&36&31&26&&-&-&-&59&\\ \end{array}$$

Lets try decrementing by $19$:

$$\begin{array}{rrrrrrrrrrrl} 03&-&-&-&-&-&&59&-&-&-&\\ &&-&??&&-&-&-&-&&&\leftarrow \text{Can't put -12, can't be negative.}\\ 13&10&07&04&&-&&-&-&-&-&\\ 32&&&20&&-&&-&&&-&\\ 51&46&41&36&31&26&&-&-&-&59&\\ \end{array}$$

What do this means?

Trying anything below $19$ would just produce negative numbers there.

Lets try decrementing by $21$:

$$\begin{array}{rrrrrrrrrrrl} 03&-&-&??&-&-&&59&-&-&-&\leftarrow \text{Can't put -06, can't be negative.}\\ &&-&00&&-&-&-&-&&&\\ 09&10&11&12&&-&&-&-&-&-&\\ 30&&&24&&-&&-&&&-&\\ 51&46&41&36&31&26&&-&-&-&59&\\ \end{array}$$

Lets try decrementing by $22$:

$$\begin{array}{rrrrrrrrrrrl} 03&02&01&00&??&-&&59&-&-&-&\leftarrow \text{Can't put -01, can't be negative.}\\ &&-&06&&-&-&-&-&&&\\ 07&10&13&16&&-&&-&-&-&-&\\ 29&&&26&&-&&-&&&-&\\ 51&46&41&36&31&26&&-&-&-&59&\\ \end{array}$$

Lets try decrementing by $23$:

$$\begin{array}{rrrrrrrrrrrl} 03&??&??&04&-&-&&59&-&-&-&\leftarrow \text{Can't put 3}\frac{1}{3}\text{and 3}\frac{2}{3}\text{, not integers.}\\ &&-&12&&-&-&-&-&&&\\ 05&10&15&20&&-&&-&-&-&-&\\ 28&&&28&&-&&-&&&-&\\ 51&46&41&36&31&26&&-&-&-&59&\\ \end{array}$$

Lets try decrementing by $25$:

$$\begin{array}{rrrrrrrrrrrl} 03&??&??&20&-&-&&59&-&-&-&\leftarrow \text{Can't put 8}\frac{2}{3}\text{and 14}\frac{1}{3}\text{, not integers.}\\ &&-&24&&-&-&-&-&&&\\ 01&10&19&28&&-&&-&-&-&-&\\ 26&&&32&&-&&-&&&-&\\ 51&46&41&36&31&26&&-&-&-&59&\\ \end{array}$$

So:

It must be decremented by $24$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&-&-&-&&&\\ 03&10&17&24&&22&&-&-&-&-&\\ 27&&&30&&24&&-&&&-&\\ 51&46&41&36&31&26&&-&-&-&59&\\ \end{array}$$

Second guess:

Now lets try something right to the $20$.

Lets try $21$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&21&22&23&&&\\ 03&10&17&24&&22&&??&-&-&-&\\ 27&&&30&&24&&??&&&-&\\ 51&46&41&36&31&26&&??&-&-&59&\leftarrow \text{Can't put -89, can't be negative.}\\ \end{array}$$

We can infer that:

For $22$, we get $-81$ in that same spot. $-73$ for $23$, $-65$ for $24$, $-57$ for $25$, $-49$ for $26$, $-41$ for $27$, $-33$ for $28$, $-29$ for $29$, $-21$ for $30$, $-13$ for $31$, $-05$ for $32$. Going for numbers smaller than $21$ will also be always negative. We can't try $47$ or higher because this would produce something too large at the end of the row starting with $20$ (putting $46$ produces $72$ and $98$).

So, lets try $33$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&33&46&59&&&\\ 03&10&17&24&&22&&33&-&-&-&\\ 27&&&30&&24&&20&&&-&\\ 51&46&41&36&31&26&&07&??&??&59&\leftarrow \text{Can't put 24}\frac{1}{3}\text{and 41}\frac{2}{3}\text{, not integers.}\\ \end{array}$$

Lets try $34$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&34&48&62&&&\\ 03&10&17&24&&22&&37&-&-&-&\\ 27&&&30&&24&&26&&&-&\\ 51&46&41&36&31&26&&15&??&??&59&\leftarrow \text{Can't put 29}\frac{2}{3}\text{and 44}\frac{1}{3}\text{, not integers.}\\ \end{array}$$

Lets try $35$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&35&50&65&&&\\ 03&10&17&24&&22&&41&-&-&-&\\ 27&&&30&&24&&32&&&-&\\ 51&46&41&36&31&26&&23&35&47&59&\\ \end{array}$$

Third guess:

Now to finish, we see that the cell at the middle line and last column, must be odd, otherwise, it is impossible to fill the cell under it. To it be odd, all the remaining cells at the middle row must be odd also.

So, lets try a $43$ under the $65$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&87&??&??&\leftarrow \text{Can't put 115 and 143, too high.}\\ &&13&18&&20&35&50&65&&&\\ 03&10&17&24&&22&&41&43&45&47&\\ 27&&&30&&24&&32&&&53&\\ 51&46&41&36&31&26&&23&35&47&59&\\ \end{array}$$

What we can try then?

Replacing the $43$ with something lower, will just make the cell above the $65$ go even higher. So we must replace it with something higher than $43$.

If we try $45$, the top-right cell will go to $137$, with $47$ will go to $131$, $49$ will go to $125$, $51$ will go to $119$, $53$ will go to $113$, $55$ will go to $107$, $57$ will go to $101$.

Then...

... lets try $59$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&71&83&95&\\ &&13&18&&20&35&50&65&&&\\ 03&10&17&24&&22&&41&59&77&95&\\ 27&&&30&&24&&32&&&77&\\ 51&46&41&36&31&26&&23&35&47&59&\\ \end{array}$$

And it is solved!

The second guess has a single solution:

Do other solutions exists?

To the left part no, because $27$ is the only number that fits above $51$ (the first guess). So lets see if some other number fits in the second and third guesses.

Right to the $20$, lets try $36$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&36&52&68&&&\\ 03&10&17&24&&22&&45&-&-&-&\\ 27&&&30&&24&&38&&&-&\\ 51&46&41&36&31&26&&31&??&??&59&\leftarrow \text{Can't put 40}\frac{1}{3}\text{and 49}\frac{2}{3}\text{, not integers.}\\ \end{array}$$

Lets try $37$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&37&54&71&&&\\ 03&10&17&24&&22&&49&-&-&-&\\ 27&&&30&&24&&44&&&-&\\ 51&46&41&36&31&26&&39&??&??&59&\leftarrow \text{Can't put 45}\frac{2}{3}\text{and 52}\frac{1}{3}\text{, not integers.}\\ \end{array}$$

Lets try $38$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&38&56&74&&&\\ 03&10&17&24&&22&&53&-&-&-&\\ 27&&&30&&24&&50&&&-&\\ 51&46&41&36&31&26&&47&51&55&59&\\ \end{array}$$

What is going on?

In fact, right to the $20$ we must produce a number which added to one is multiple of $3$, otherwise the last line would not be able to hold integers. We already know that numbers lower than $35$ produce negative numbers in the $8$th column and that numbers greater than $46$ produces numbers greater than $100$ in the row starting with $20$. So, we may try only $35$, $38$, $41$ and $44$ in the place at the right side of the $20$. Further, we know that $35$ is able to solve the puzzle.

Continuing with the $38$, we must put some number below the $74$ which do not produces something too large in the upper right cell. The lower the number under $74$ is, the higher the number above it is. But, the higher it is, higher will be the number in the end of the middle row also. Further, this number must be odd, otherwise we get an even number in the end of the middle row and the number just below it would not be integer.

So, lets try $73$:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&75&91&??&\leftarrow \text{Can't put 107, too high.}\\ &&13&18&&20&38&56&74&&&\\ 03&10&17&24&&22&&53&73&93&??&\leftarrow \text{Can't put 113, too high.}\\ 27&&&30&&24&&50&&&-&\\ 51&46&41&36&31&26&&47&51&55&59&\\ \end{array}$$

What do this means?

If we try something smaller than $73$ below the $74$, the number on the top-right will grow. If we try something larger, then the number on the end of the middle row will grow. So it is impossible with $38$ at the right of the $20$.

If we try $41$, we get $83$ in the end of the row starting with $20$. If we try $44$, we get $92$. And these numbers are far higher than $53$ and $59$, so either the middle or the top row would end with something higher than $100$. This proves that right to the $20$, the number must be $35$, so the second guess has a single solution.

The third guess has a single solution:

Lets remember where it is before the third guess:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&35&50&65&&&\\ 03&10&17&24&&22&&41&-&-&-&\\ 27&&&30&&24&&32&&&-&\\ 51&46&41&36&31&26&&23&35&47&59&\\ \end{array}$$

What can we try?

We already know that below the $65$ the number must be odd and can't be lower than $59$ ($59$ solves it) because it would make the top-right number be higher than $100$. So we must try something higher than $59$.

What happens if we try $61$?

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&-&-&-&\\ &&13&18&&20&35&50&65&&&\\ 03&10&17&24&&22&&41&61&81&??&\leftarrow \text{Can't put 101, too high.}\\ 27&&&30&&24&&32&&&-&\\ 51&46&41&36&31&26&&23&35&47&59&\\ \end{array}$$

What do this means?

If we increase the number below $65$, the last number in the middle row will just go even higher. This way, the third guess can't be lower than $59$ nor higher than $59$, so $59$ is the only number where it works, and thus the third guess has a single solution.

So I proved that there is only one solution, and that this solution is:

$$\begin{array}{rrrrrrrrrrrl} 03&06&09&12&15&18&&59&71&83&95&\\ &&13&18&&20&35&50&65&&&\\ 03&10&17&24&&22&&41&59&77&95&\\ 27&&&30&&24&&32&&&77&\\ 51&46&41&36&31&26&&23&35&47&59&\\ \end{array}$$

$\endgroup$
  • $\begingroup$ Excellent path of deduction. +1 from me. Edit in "spoiler" tags for bonus, please. $\endgroup$ – BmyGuest Dec 14 '14 at 18:51
  • $\begingroup$ Downvoter, could you explain what you think is wrong here? $\endgroup$ – Victor Stafusa Dec 14 '14 at 19:42
7
$\begingroup$

enter image description here

This is considering arithmetic progression as sequence alone

Steps:

The given sequence at the bottom has to be filled i.e. 26 31 up to 51 (E6 to E1) Then since 51 has to be filled up the number 2 rows above has to be odd number otherwise the row just above 51 cannot be filled with a whole number.

Considering the above and also considering that if we enter a number above 51 in cell C1 then since 10 is fixed at C2, the series (C1,C2...) would go to negative, the number has to be lower than 51 and cannot be higher than 19 or less than 1 (for in both these scenarios the adjacent numbers would become negative), once you choose a number and start filling the story will unfold gradually, just 2 constraints no number can go below 0 or above 99. If you try various numbers for C1 you will notice that the constraints would get violated for one of the cells (I tried many :) believe me, but feel free to try others, it either increases one number above 99 or decreases one below 0) so C1 has to be 3 which will fill the entire left side leaving B6 at 20. Then the tricky part is managing the right side with the two 59 constraints

$\endgroup$
  • $\begingroup$ Huh, edits are flying in! I like your logic, but it gets a tiny bit jumpy at "...once you choose a number...will unfold gradually..." C1 has to be 3. I'm withholding my +1 for now ;c) $\endgroup$ – BmyGuest Dec 14 '14 at 18:45
  • $\begingroup$ @BmyGuest thanks, yes I edited various parts leaving some gaps have a look now :) $\endgroup$ – skv Dec 14 '14 at 18:46
  • 2
    $\begingroup$ seems to be come a typing race rather than a puzzle race ;c) I was thinking of a solution-track alongside Victor's below. But I think both of you have done more or less the same... His (currently) is more complete, yours visually nicer (which slowed you down). +1 for both, I'd say. $\endgroup$ – BmyGuest Dec 14 '14 at 18:49
  • $\begingroup$ @BmyGuest yes this was just a race no doubt, I went along the thought process that Victor suggested :) but I made some quick assumptions which probably made me faster $\endgroup$ – skv Dec 14 '14 at 18:50
1
$\begingroup$

One of the solution that I could find is :
enter image description here

Steps :
1. Begin with the given sequence at f5 and e5.
2. The number at d1 must be such that : (d5-d1) must be divisible by 4 and (d1-a1) must be divisible by 3. So it must be 12/24. Using brute force elimination, it comes out to be 12.
The first half then can be solved easily.
3. Similarly for the second half, the number at h5 must be such that : (k5-h5) must be divisible by 3 and (h1-h5) must be divisible by 4. So it must be 11/23/35... Again using brute force elimination it is 23.

$\endgroup$
0
$\begingroup$

There is a unique solution:

enter image description here

To find it, consider

enter image description here

The value of $X$ can be at most $28$ (because of the $10$ in the same row), so $Y$ can be at most $16$. However, $Y\equiv 36\mod 4$ and $Y\equiv 3\mod 3$, so we must have $Y=12$. This allows us to fill in up to here:

enter image description here

Here $Y=3/2 X-10$. The sequence $59+P$, $A+Q$, $B+R$, $C+S$ is an arithmetic progression, and the first two terms are $2X$ and $2Y$, so we get $C+S=5X-60$.

$\endgroup$
  • $\begingroup$ I don't doubt your reasoning, but can you expand on the argument "The value of X can be at most 28 (because of the 10 in the same row" Not sure I'm seeing it. Skv's argument above seems 'easier' as starters.) $\endgroup$ – BmyGuest Dec 14 '14 at 18:38
0
$\begingroup$

enter image description here

Here is my answer. For explanation purpose I named the board like chess. X-Axis is labeled as a - k. Y-Axis is labeled as 1-5.

My approach :

  1. In e5 and f5 we have adjacent numbers. So we know the diff is 5. So work the row upto a5.

  2. Since the number at a5 is odd, the number at a3 should also be Odd ! number at a3 cannot be 9,7,5 because then the number at d5 become -ve. Once you get the number a3 as 3, the rest (left half of the board) can be worked out easily.

  3. For the right half - Lets assume the number in h5 is N. And lets assume the delta in column h is 'y' and delta in row 5 (from h5 to k5) is 'x'. So

    N = 59 + 4y

    N = 59 + 3x

So we get 3x = 4y. Once you assume x = 4 and y = 3 then the rest can be worked out.

Note: There are multiple solutions to this which can be worked out by trying different values at a3 and different values of x and y.

$\endgroup$
  • 3
    $\begingroup$ I am afraid the problem requested integers less than 100. $\endgroup$ – Florian F Jan 7 '15 at 15:47

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.