Waste less time on Facebook — follow Brilliant.
×

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 Paramjit Singh
4 years ago

No vote yet
10 votes

Comments

Sort by:

Top Newest

  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.

Mark Hennings - 4 years ago

Log in to reply

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

Paramjit Singh - 4 years ago

Log in to reply

Doesn't the result in problem \(2\) follow directly from symmetry?

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

Log in to reply

  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.

Mark Hennings - 4 years ago

Log in to reply

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

Paramjit Singh - 4 years ago

Log in to reply

\[\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.

Log in to reply

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'\)).")

Paramjit Singh - 4 years ago

Log in to reply

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\).

Paramjit Singh - 4 years ago

Log in to reply

  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\)

Samuel Queen - 3 years, 12 months ago

Log in to reply

EDIT: this is for problem 2 not 1.

Samuel Queen - 3 years, 12 months ago

Log in to reply

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

Log in to reply

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,

Paramjit Singh - 4 years ago

Log in to reply

Thanks. Corrected.

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...