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)

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

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?

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.

## Comments

Sort by:

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

Log in to reply

Perfect. Thank you sir. Can't believe these proofs were so trivial. – Paramjit Singh · 3 years, 10 months agoLog in to reply

EDIT: Never mind, your proof is a more rigorous version of mine. :) – Sreejato Bhattacharya · 3 years, 10 months ago

Log in to reply

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.

Log in to reply

– Paramjit Singh · 3 years, 10 months ago

Thanks. Nice solution to both \((1)\) & \((2)\).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. – Sreejato Bhattacharya · 3 years, 10 months ago

Log in to reply

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 · 3 years, 10 months agoLog in to reply

Some previous problems:- (As such, Mark H. & Siddhartha S. have already given

perfectsolutions to these.)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}\).

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

Show that the number \(11...11\) with \(3^n\) digits is divisible by \(3^n\).

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

Show that if a prime number is divided by \(30\), then the remainder is either a prime or \(1\).

Log in to reply

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

Log in to reply

– Samuel Queen · 3 years, 10 months ago

EDIT: this is for problem 2 not 1.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 – Siddhartha Srivastava · 3 years, 10 months ago

Log in to reply

Typo: 7th line end: It should be \(2*3^n\) 0's, – Paramjit Singh · 3 years, 10 months ago

Log in to reply

– Siddhartha Srivastava · 3 years, 10 months ago

Thanks. Corrected.Log in to reply