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.

No vote yet

10 votes

×

Problem Loading...

Note Loading...

Set Loading...

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

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

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

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

Log in to reply

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.

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

Perfect. Thank you sir. Can't believe these proofs were so trivial.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,

Log in to reply

Thanks. Corrected.

Log 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

EDIT: this is for problem 2 not 1.

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'$).")Log in to reply