# [Calvin] Which solution would you feature? (2)

Below, we present a problem from the 12/24 Algebra and Number Theory set, along with 3 student submitted solution. You may vote up or down for the solutions that you think should be featured / or are wrong. Also, feel free to make remarks about these solutions. Note - This is the hardest problem that was available just to Level 4 and 5 users. A solution should not receive votes just because "it only uses simple math."

Problem: System of equations with no solutions For what integer $$0 < n < 1000$$, does the following system of n linear equations have no complex solution? $\begin{array}{ l l l l l l } -10a_1 & + a_2 & + a_3 & + \ldots & + a_n &= 9 \\ a_1 & - 10a_2 &+ a_3 & + \ldots & + a_n &= 99 \\ a_1 & + a_2 & - 10 a_3 & + \ldots & + a_n &= 999 \\ \vdots & & & & &\vdots \\ a_1 & + a_2 & + a_3 & + \ldots & - 10 a_n & = 10^n-1 \\ \end{array}$

You may try the problem by clicking on the above link.

All solutions have LaTeX edits to make the math appear properly. The exposition is presented as is, and have not been edited.

Remarks from Calvin

$\mbox{Note on "sufficient conditions and necessary conditions"}$

All too often, solutions fail to distinguish between necessary conditions, and sufficient conditions. A necessary condition is one that must be satisfied in order for the condition to hold. Even if this condition is satisfied, we do not know if the statement is true. A sufficient condition, is one that if satisfied, the statement is true. However, it doesn't mean that there are no other possible conditions. As an example, consider if we're looking for solutions to $$x^2=1$$. Then, a necessary condition is that $$x^4=1$$, while a sufficient condition is $$x=1$$.

Solution A - In this solution, it first attempts to find values of $$\{a_1, a_2, \ldots, a_n\}$$, through the process of elimination. In this case, he has stated a necessary, but not sufficient condition. We do not know that a solution set must exists, merely conditions that must be true in order for it to exist. Care has to be placed that we do not get an inconsistent set of solutions, which the problem is after.

Secondly, Even though "When we divided the sum of the equations by n−11, we had to assume that n−11≠0" is true, the conclusion "so when n=11, the equations are unsolvable." does not necessarily follow. For example, $$(n-11))(a_1 + a_2) = 0$$ has solutions, even when $$n=11$$. In this case, he has stated a sufficient, but not necessary, condition. We do not know that no solutions can exist; in fact, we do not know anything as yet, apart from the author identifying a case where he might have done division by 0. Care has to be placed in ensuring that the statements we make are accurate, and follow directly from each other.

Solution B - This solution is much better, in explaining the steps and doing the calculations to find the values of $$a_i$$, it is easy to see why the statements listed in the problem must now hold. Furthermore, it provides a proper justification why $$n=11$$ has no possible solution.

This solution is presented by Wang Jianzhi.

Solution C - This solution tries to be too clever in applying the augmented matrix. Firstly, it doesn't explain why the matrix must be of full rank. This is the non-trivial part of the calculation, and can be obtained by row reduction, or knowing the determinant. Secondly, it forgets to actually check the conditions for existence of solutions, which is independent of the rank of the matrix. Having full rank only guarantees that a unique solution exists, otherwise, we could have 0, 1, or infinitely many solutions.

Note by Calvin Lin
5 years, 10 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Solution B - Firstly we add all the equations. $$LHS = (n–11)(a_1 + a_2 + a_3 + ... + a_n)$$ $$RHS = 9 + 99 + 999 + ... + 10^n –1$$ When $$n \neq 11$$ , we can get : $$a_1 + a_2 + a_3 + ... + a_n = \frac {9 + 99 + 999 + ... + 10^n –1}{n–11}$$. Then, we use it to minus off each equation in the system. We can get $$11a_i = \frac {9 + 99 + 999 + ... + 10^n –1}{n–11} – 10^i +1$$ for $$i = 1, 2, 3, ... , n$$. Then, we can easily get the solutions for the system. When n = 11, $$LHS = (11–11)(a_1 + a_2 + a_3 + ... + a_{11}) = 0$$ $$RHS = 9 + 99 + 999 + ... + 10^{11} –1$$ Clearly $$0 \neq 9 + 99 + 999 + ... + 10^{11} –1$$ so $$LHS \neq RHS$$ and 11 is the only number which the system doesn't admit a solution.

Staff - 5 years, 10 months ago

Solution A - Imagine, given some $$n$$, how to actually solve the system of equations. One of the easiest ways would be to add up all the equations and divide by $$n-11$$. This will result in an equation with a coefficient of one for each variable. From there, we could take this new equation and subtract the first equation to obtain an equation with only $$a_1$$, which can be easily solved to find the value of $$a_1$$. Similarly, we can subtract the second equation to get the value of $$a_2$$, and so on. Using this method, we can solve this system for any $$n$$, with one important exception. When we divided the sum of the equations by $$n-11$$, we had to assume that $$n-11\neq0$$, so when $$n=11$$, the equations are unsolvable.

Staff - 5 years, 10 months ago

Remarks have been updated. Especially read the comment about "necessary conditions and sufficient conditions".

Staff - 5 years, 10 months ago

@Lawrence Perfect, that was how this question was developed, and is the 1-line explanation / understanding of the problem. Of course, they are other ways of approaching it, and I'm glad to know that you're thinking of it in this way. Why don't you email me your solution?

Staff - 5 years, 10 months ago

No, in my opinion Solution C is not rigorous enough because there never show the computation of the rank which is essential.

- 5 years, 10 months ago

Solution C - Here we construct a augmented matrix

$\left[ \begin{array}{c c c c c c} -10 &1& &1 &1\ldots &1 \\ 1 &-10 &1 &1&\ldots &1 \\ 1 &1 &-10 &1&\ldots &1 \\ \vdots & & & & & \vdots\\ 1 &1 &1 &1 &\ldots &-10 \\ \end{array} \right| \left. \begin{array}{c} 9\\ 99\\ 999\\ \vdots\\ 10^n-1\\ \end{array} \right]$

Now rank of augmented matrix and rank of coefficient are different if $$n = 11$$. therefore the system of equation is inconsistent if $$n=11$$.

Staff - 5 years, 10 months ago

Well computing the rank is essentially a restatement of the problem which is why I feel like omitting the computation makes it not a solution. How I solved this problem was computing the determinant by looking at the eigenvalues, and you get 0 is an eigenvalue iff n=11.

- 5 years, 10 months ago

@Lawrence, Apart from showing the computation of the rank, what else is essential? Would it be easier to compute something else instead?

Staff - 5 years, 10 months ago

@Lawrence, You will submit Solution C? Without any edits?

Staff - 5 years, 10 months ago

I'd just like to note there is a nice solution using eigenvalues and properties of circulant matrices, if I had the opportunity to submit a solution I would have submitted thise one!

- 5 years, 10 months ago