Product of all such expressions is a positive integer

If P(n)P(n) denotes the product of all the numbers of the form ±1±2±3±±n\pm \sqrt{1} \pm \sqrt{2} \pm \sqrt{3}\pm \cdots \pm \sqrt{n} where ±\pm are chosen arbitrarily.

Then prove that P(n)P(n) is a positive integer n2\forall n \geq 2.

(Can we find that positive integer?)

Note by Kartik Sharma
4 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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]( 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×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}


Sort by:

Top Newest

Here's my attempt: Call this set SS. The set SS has 2n2^{n} members. No such member can be zero. There is a one-one correspondence between a positive member xSx \in S and xS-x \in S (note that both xx and x-x will belong to this set and this is seen by switching all the signs). Their product is x2<0-x^2 < 0. And the number of such pairs is 2n/2=2n12^n/2 = 2^{n-1}. For n2n \ge 2, this is an even natural number. And the product of an even number of pairs, where the product of each pair is negative, is of course, positive.

Parth Kohli - 4 years, 2 months ago

Log in to reply

My try is as follows.

Let Pn1(x)=a2n1x2n1+a2n11x2n11++a1x1+a0P_{n-1}(x) = a_{2^{n-1}}x^{2^{n-1}} + a_{2^{n-1}-1}x^{2^{n-1}-1} + \cdots + a_1 x^1 + a_0

be the polynomial having roots as numbers of the form ±1±2±3±±n1\pm \sqrt{1} \pm \sqrt{2} \pm \sqrt{3} \pm \cdots \pm \sqrt{n-1}

Then, Pn(x)P_n(x) has roots as Root ofPn1(x)±n\text{Root of} P_{n-1}(x) \pm \sqrt{n}. Thus we can transform it as-

Pn(x)=(a2n1(xn)2n1+a2n11(xn)2n11++a1(xn)1+a0)(a2n1(x+n)2n1+a2n11(x+n)2n11++a1(x+n)1+a0)P_n(x) = (a_{2^{n-1}}{(x-\sqrt{n})}^{2^{n-1}} + a_{2^{n-1}-1}{(x-\sqrt{n})}^{2^{n-1}-1} + \cdots + a_1 {(x-\sqrt{n})}^1 + a_0)(a_{2^{n-1}}{(x+\sqrt{n})}^{2^{n-1}} + a_{2^{n-1}-1}{(x+\sqrt{n})}^{2^{n-1}-1} + \cdots + a_1 {(x+\sqrt{n})}^1 + a_0)

Proposition: Pn(x)is a polynomial having integer coefficientsP_n(x) \text{is a polynomial having integer coefficients}

We prove this using induction.

Base Case - n=1:x21=0n = 1 : x^2 -1 = 0

Assuming for n1n-1, let's try for nn,

[xk]Pn(x)=b+c=k(m=02n1(mb)am(n)mb)(t=02n1(tc)at(n)tc)\displaystyle [x^k]{P_n(x)} = \sum_{b + c = k}{\left(\sum_{m=0}^{2^{n-1}}{\binom{m}{b} a_m {(\sqrt{n})}^{m-b}}\right)\left(\sum_{t=0}^{2^{n-1}}{\binom{t}{c} a_t {(-\sqrt{n})}^{t-c}}\right)}

(Oh, that is scary, but it is not required).

We can get a n\sqrt{n} term left if mb=Odd,tc=Evenm-b = \text{Odd}, t-c = \text{Even} or tc=Odd,mb=Event-c = \text{Odd}, m-b = \text{Even}

Now, an irrational term or a non-integer term(in this case), will be left if either

mb=Odd,tc=Evenm-b = \text{Odd}, t -c = \text{Even}


mb=Even,tc=Oddm-b = \text{Even}, t -c = \text{Odd}.

And now if there is a case like (mb,tc)=(1,2)(m-b, t-c) = (1,2), then there will also be a case like (mb,tc)=(2,1)(m-b,t-c) = (2,1). Note that this counter-case will not be there if mb=tcm-b = t-c but then their parity is same too, so they will not be considered.

Since by interchanging (m,b)(t,c)(m,b) \rightarrow (t,c), we change the coefficient of n(m+tbc)/2n^{(m+t-b-c)/2}from

(mb)(tc)amat(mb)(tc)amat\binom{m}{b}\binom{t}{c}a_m a_t \rightarrow -\binom{m}{b}\binom{t}{c}a_m a_t

all the numbers with fractional powers cancel out and only integers remain.

By observing the general polynomial recurrence we can see that leading coefficient is given by

an=an12;a1=1    an=1a_n = a_{n-1}^2; a_1 = 1 \implies a_n = 1

And we have just proven that all the other coefficients are integers.

Therefore, all symmetric products of numbers of the form ±1±2±±n\pm \sqrt{1} \pm \sqrt{2} \pm \cdots \pm \sqrt{n} is an integer.

Kartik Sharma - 4 years, 6 months ago

Log in to reply

It's slightly hard to follow exactly what you're doing, but I believe you have the right idea.

In the final line, I believe you mean "product" instead of "sum".

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

Oops, yeah. Fixed it! What part exactly is not clear? Maybe the formatting isn't good.

Kartik Sharma - 4 years, 5 months ago

Log in to reply

@Kartik Sharma

  1. Explaining the roots transformation better. (I agree that what you're doing works, but you should be explaining it for others to easily understand why what you're doing works)

  2. Note that the induction should start with n=2 n = 2 .

  3. Note that you want to show the product is positive, which has been ignored. In particular, looking at n=1n = 1 , you should realize that the product is 1 -1 (which is why we have to start with n=2 n = 2 ).

  4. Justifying the formula for [xk]Pn(x) [ x^k ] P_n(x) . At least give a verbal description of how that is arrived at.

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

Hey,great solution.BTW you are in which class?

A Former Brilliant Member - 4 years, 6 months ago

Log in to reply

Class XII.

Kartik Sharma - 4 years, 6 months ago

Log in to reply

You have immense amount of knowledge as compared to a 12th grader!!!!

A Former Brilliant Member - 4 years, 6 months ago

Log in to reply

@A Former Brilliant Member I just have a good amount of time to devote to science and mathematics.

Kartik Sharma - 4 years, 6 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...