# Proof Problems

Here I list some problems,which I got while practicing. Help is solicited. Thanks. (The discussion has been updated, you may check out the comments for the previous problems I posted)

1. Prove that given any prime $p$, there exist infinitely many positive integers $n$, such that $p| n2^{n-1}+1$.

2. If every point of the plane is painted one of three colors, do there necessarily exist two points of the same color exactly one inch apart?

3. Let $n>1$ is an odd integer. Show that the sequence

$\displaystyle {n \choose 1},{n \choose 2},...,{n \choose \frac{n-1}{2}}$ has an odd number of odd integers.

Note by A Brilliant Member
5 years, 8 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:

1. Multiply out by $x(x+1)(x+2)\cdots(x+n)$ and put $x=-k$ to evaluate $A_k$.

2. If $A,B,C$ are odd integers and $\tfrac{a}{b}$ is a root of $AX^2 + BX + C = 0$, where $a,b$ are coprime integers, then $Aa^2 + Bab + Cb^2 = 0$. But since $A,B,C$ are all odd and $a,b$ are coprime (and so not both even) $Aa^2 + Bab + Cb^2$ must be odd, giving you a contradiction.

- 5 years, 8 months ago

Thanks. Nice solution to both $(1)$ & $(2)$.

- 5 years, 8 months ago

1. We have $3n+1 = a^2$, and so $3n = (a-1)(a+1)$. There are two cases to consider. If $3$ divides $a-1$, then $a = 3m+1$, so $n = m(3m+2)$, and hence $n+1 = 3m^2 + 2m + 1 = m^2 + m^2 + (m+1)^2$. If $3$ divides $a+1$ then $a = 3m+2$, so $n = (3m+1)(m+1)$, and hence $n+1 = 3m^2 + 4m + 2 = m^2 + (m+1)^2 + (m+1)^2$.

2. The sum of the numbers from $1$ to $50$ is $1275$, which is odd. Thus if $A$ is any subset of $\{1,2,\ldots,50\}$ and $A' = \{1,2,\ldots,50\} \backslash A$ is its complement, then the sum of the elements in $A$ and the sum of the elements in $A'$ together add to the odd number $1275$, and hence one must be even and the other odd. Thus the operation of complementation is a bijective map from the set of subsets of $\{1,2,\ldots,50\}$ with odd sum to the set of subsets of $\{1,2,\ldots,50\}$ with even sum. Since there are $2^{50}$ subsets of $\{1,2,\ldots,50\}$, exactly half of them, namely $2^{49}$, have an odd sum.

- 5 years, 8 months ago

Doesn't the result in problem $2$ follow directly from symmetry?

EDIT: Never mind, your proof is a more rigorous version of mine. :)

- 5 years, 8 months ago

Perfect. Thank you sir. Can't believe these proofs were so trivial.

- 5 years, 8 months ago

3.

Base Case : When $n = 1$;

$111$ is divisible by $3$.

Inductive Case : If $11\ldots11$ with $3^n$ digits is divisible by $3^n$,

For n+1, $11\ldots11$ with $3^{n+1}$ digits

$= 11\ldots11 + 11\ldots1100\ldots00 + 11\ldots1100\dots00$

With the first term having $3^n$ 1's, the second term $3^n$ 1's and 0's, and the last term with $3^n$ 1's and $2 * 3^{n}$ 0's.

$= 11\dots11(1 + 10^{3^n} + 10^{2*3^n})$

$= 11\dots11(10\dots010\dots01)$

The first part is divisible by $3^n$ and the second by $3$. Therefore, their product is divisible by $3^{n+1}$

4.

$\gcd( n^2 + 20, n^2 + 2n + 21)$

Subtracting the first term from the second,

$= \gcd( n^2 + 20, 2n + 1)$

Multiplying the first term with 4 won't change the gcd since 2n + 1 is odd.

$= \gcd( 4n^2 + 80, 2n + 1)$

Dividing the first term by the second

$= \gcd( 81,2n+1)$

Since the gcd is the greatest common DIVISOR of 81 and 2n + 1, it will divide 81.

5.

Applying the Euclidean Division lemma to p and 30, we get,

$p = 30q + r, 0 \leq r < 30$

If r is divisble by 2,3 or 5, It would imply p is divisible by 2,3 or 5, which is not possible. Therefore r is not divisible by 2,3 or 5.But every composite number below 30 contains a factor of 2,3 or 5. Therefore r is prime or equal to 1

- 5 years, 8 months ago

Awesome! Check back for some updates to this thread. I myself got Q4 2 hours after I posted. Thanks!

Typo: 7th line end: It should be $2*3^n$ 0's,

- 5 years, 8 months ago

Thanks. Corrected.

- 5 years, 8 months ago

Some previous problems:- (As such, Mark H. & Siddhartha S. have already given perfect solutions to these.)

1. In the identity $\frac{n!}{x(x+1)(x+2)...(x+n)} = \displaystyle \sum_{k=0}^n \frac{A_k}{x+k}$, prove that: $A_k = (-1)^k {n \choose k}$.

2. If the coefficients of a quadratic equation are all odd integers, show that its roots can not be rational.

3. Show that the number $11...11$ with $3^n$ digits is divisible by $3^n$.

4. For a natural number $n$, let $a_n = n^2 + 20$. Show that $\gcd(a_n,a_{n+1}) | 81$.

5. Show that if a prime number is divided by $30$, then the remainder is either a prime or $1$.

- 5 years, 8 months ago

1. The fact will follow from Lemma: if $n$ is not a perfect square then $\sqrt{n}$ is irrational. Proof: suppose $\frac{i^{2}}{j^{2}} = n$ if $p|i$ $p$ a prime then $p^{2}|n$. Hence $i^{2}|n \Longrightarrow 1 = \frac{nj^{2}}{i^{2}} \Longrightarrow \frac{n}{i^{2}} = j^{2} = 1$ because $n,i,j$ are positive integers and $i^{2}|n$.
Now the problem is equivalent to showing that $b^{2} - 4ac$ is not a perfect square. Because $ac$ is odd $b^{2} - 4ac$ is congruent to $b^{2} + 4$ modulo $8$. But because $b$ is odd $b^{2} = 1 + 8k \Longrightarrow b^{2} - 4ac = 5 + 8k$ witch is not a perfect square because $5$ is not a quadratic residue $(mod8) Q.E.D$

- 5 years, 7 months ago

EDIT: this is for problem 2 not 1.

- 5 years, 7 months ago

$\text{\#}2$ From symmetry one can conclude that the number of subsets with odd sum of elements is equal to the number of subsets with even sum of elements. Since there are a total of $2^{50}$ subsets, it immediately follows that there are $2^{49}$ subsets with odd element sum.

EDIT: @Paramjit I used that idea. I'm sorry, I just provided a bare sketch of a proof.

- 5 years, 8 months ago

Mark H. has used the same basic idea perfectly. You need to show that sum of the numbers from $1$ to $n$ is odd, here, else your proof is not complete. (In general, it is easy to know from Mark's solution that "If $n = 2k = k +k$ is even, number of odd-sum subsets outnumbers the even-sum subsets when $k$ is odd & opposite when $k$ is even (as $n = 4k' = 2k'+2k'$).")

- 5 years, 8 months ago