[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}$

Clarification: If the system always admits a solution, type your answer as 0. If there are multiple cases where the system doesn't admit a solution, type in any one of your answers.

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.

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 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"

Math

Appears 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}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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.

Calvin Lin Staff - 8 years, 5 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.

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

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$ .

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

Lawrence Sun - 8 years, 5 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?

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!

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

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

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.

Math	Appears 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}$