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 pp, there exist infinitely many positive integers nn, such that pn2n1+1p| 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>1n>1 is an odd integer. Show that the sequence

(n1),(n2),...,(nn12)\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

No vote yet
10 votes

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

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

Mark Hennings - 5 years, 8 months ago

Log in to reply

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

A Brilliant Member - 5 years, 8 months ago

Log in to reply

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

  2. The sum of the numbers from 11 to 5050 is 12751275, which is odd. Thus if AA is any subset of {1,2,,50}\{1,2,\ldots,50\} and A={1,2,,50}\AA' = \{1,2,\ldots,50\} \backslash A is its complement, then the sum of the elements in AA and the sum of the elements in AA' together add to the odd number 12751275, 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,,50}\{1,2,\ldots,50\} with odd sum to the set of subsets of {1,2,,50}\{1,2,\ldots,50\} with even sum. Since there are 2502^{50} subsets of {1,2,,50}\{1,2,\ldots,50\}, exactly half of them, namely 2492^{49}, have an odd sum.

Mark Hennings - 5 years, 8 months ago

Log in to reply

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

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

Sreejato Bhattacharya - 5 years, 8 months ago

Log in to reply

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

A Brilliant Member - 5 years, 8 months ago

Log in to reply

3.

Base Case : When n=1 n = 1 ;

111 111 is divisible by 33.

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

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

=1111+11110000+11110000 = 11\ldots11 + 11\ldots1100\ldots00 + 11\ldots1100\dots00

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

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

=1111(1001001) = 11\dots11(10\dots010\dots01)

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

4.

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

Subtracting the first term from the second,

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

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

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

Dividing the first term by the second

=gcd(81,2n+1) = \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,0r<30 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

Siddhartha Srivastava - 5 years, 8 months ago

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 23n2*3^n 0's,

A Brilliant Member - 5 years, 8 months ago

Log in to reply

Thanks. Corrected.

Siddhartha Srivastava - 5 years, 8 months 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 n!x(x+1)(x+2)...(x+n)=k=0nAkx+k\frac{n!}{x(x+1)(x+2)...(x+n)} = \displaystyle \sum_{k=0}^n \frac{A_k}{x+k}, prove that: Ak=(1)k(nk)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...1111...11 with 3n3^n digits is divisible by 3n3^n.

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

  5. Show that if a prime number is divided by 3030, then the remainder is either a prime or 11.

A Brilliant Member - 5 years, 8 months ago

Log in to reply

  1. The fact will follow from Lemma: if nn is not a perfect square then n\sqrt{n} is irrational. Proof: suppose i2j2=n\frac{i^{2}}{j^{2}} = n if pip|i pp a prime then p2np^{2}|n. Hence i2n1=nj2i2ni2=j2=1i^{2}|n \Longrightarrow 1 = \frac{nj^{2}}{i^{2}} \Longrightarrow \frac{n}{i^{2}} = j^{2} = 1 because n,i,jn,i,j are positive integers and i2ni^{2}|n.
    Now the problem is equivalent to showing that b24acb^{2} - 4ac is not a perfect square. Because acac is odd b24acb^{2} - 4ac is congruent to b2+4b^{2} + 4 modulo 88. But because bb is odd b2=1+8kb24ac=5+8kb^{2} = 1 + 8k \Longrightarrow b^{2} - 4ac = 5 + 8k witch is not a perfect square because 55 is not a quadratic residue (mod8)Q.E.D(mod8) Q.E.D

Samuel Queen - 5 years, 7 months ago

Log in to reply

EDIT: this is for problem 2 not 1.

Samuel Queen - 5 years, 7 months ago

Log in to reply

#2\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 2502^{50} subsets, it immediately follows that there are 2492^{49} subsets with odd element sum.

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

Sreejato Bhattacharya - 5 years, 8 months ago

Log in to reply

Mark H. has used the same basic idea perfectly. You need to show that sum of the numbers from 11 to nn 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+kn = 2k = k +k is even, number of odd-sum subsets outnumbers the even-sum subsets when kk is odd & opposite when kk is even (as n=4k=2k+2kn = 4k' = 2k'+2k').")

A Brilliant Member - 5 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...