/sci/ - Science & Math

I quit.

Qin always brings a term x^n with n>1.
This always gives an odd term more than Qi1.

>>4187451
And I mean 'coefficient', not 'term'.

Isn't this question fairly trivial?

>>4187504
Then how about you solve it.

What does "For i - 0, 1, 2, ..." mean? Is it saying "for i, where i can take on values like 0, 1, 2, ..." or does the long dash signify something I'm ignorant of? Taking it to be "for i minus 0, 1, 2, ..." doesn't make very much sense in this context to me...

Easily, the problem reduces to showing that <span class="math">o(Q_i)\leqo(Q_i+Q_j),i\neqj[/spoiler]

if <span class="math">(1+x)^{n^2}mod(2)=(1+x^{n^2})mod(2)[/spoiler] (proof can be done by induction, mod acting on the coefficients)

From this we can decompose any Qi:
<span class="math">(1+x)^{i}=(1+x)^{2^{m_{x}}}...(1+x)^{2^{m_{1}}}=(1+x^{2^{m_{x}}})...(1+x^{2^{m_{1}}})=1+x^{2^{m_{1}}
}+x^{2^{m_{2}}}+x^{2^{m_{1}}+2^{m_{2}}}+...[/spoiler] (all coefficients everything mod 2)
The last part of the equation is all the ways to sum the m_i's in any combination

From this we can also decompose any Qj:
<span class="math">(1+x)^{j}=(1+x)^{2^{n_{x}}}...(1+x)^{2^{n_{1}}}=(1+x^{2^{n_{x}}})...(1+x^{2^{n_{1}}})=1+x^{2^{n_{1}}
}+x^{2^{n_{2}}}+x^{2^{n_{1}}+2^{n_{2}}}+...[/spoiler] (all coefficients everything mod 2)


Any time a term appears in both Qi and Qj mod 2, that term has an odd coefficient in Qi+Qj, but an even coefficient in Qi+Qj
Any time a term appears in Qj, but not Qi mod 2, that term has an even coefficient in Qi+Qj, but an odd coefficient in Qi+Qj
If a term in Qj mod 2 is 0, that term will not change the odd coefficient count.


let F = 2^(number of digits that both <span class="math">2^i~and~2^j[/spoiler] are one in base 2)
let G = 2^(number of digits that are 0 in <span class="math">2^i[/spoiler], but 1 in <span class="math">2^j[/spoiler] is 1 in base 2)

The number of coefficients flipping from odd to even from Qi to Qi+Qj occurs is F

The number of times even flipping to odd from Qi to Qi+Qj occurs is G*F-F = F*(G-1)

Since (number of digits that are 0 in <span class="math">2^i[/spoiler], but 1 in <span class="math">2^j[/spoiler] is 1 in base 2) >= 1 since i and j are different, G >= 2

Thus the number of coefficients flipping from odd to even from Qi to Qi+Qj is less than or equal to the number of coefficients flipping from even to odd from Qi to Qi+Qj.

Thus <span class="math">o(Q_i)\leqo(Q_i+Q_j),i\neqj[/spoiler], which solves the problem

Sorry for the bad notation, lack of complete rigor, blah, blah, blah.

>>4187550
edit top and bottom line:
<span class="math">o(Q_i)\leq~o(Q_i+Q_j),i\neqj[/spoiler]

>>4187550
edit top and bottom line (take 2):
<span class="math">o(Q_{i})\leq o(Q_{i}+Q_{j}),i≠j[/spoiler]

>>4187550
>Easily, the problem reduces to showing that Unknown control sequence <span class="math">o(Q_i)\leq o(Q_i+Q_j),i\neq j[/spoiler]
Prove it.
I don't see how this could be enough.

>>4187562
I dunno why I thought that...
Oh well, I don't feel like starting over or finding a way to modify it. Good luck on it.

>the number of odd coefficients is denoted by o(P)
>OP
well, I guess the number of odd coefficients is a faggot.

>>4187825
I thought they were Landau symbols, at first.
>OP, a faggot
The first mod in years to do something with /sci/, a faggot? Not really.

>>4187856
>2011
>not getting jokes

>>4187428
This seems long, annoying and not at all interesting. Not even attempting than.

>>4187946
interestion, tell as more about that

Okay, so basically, we're asked what happens when we take Pascal's triangle modulo 2, and we add, to a given line, a number of lines further into the triangle.

Pascal's triangle modulo 2 looks like this:
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

As you can see, there is a lot of structure. I don't know how to prove this, but it looks like if you fix a line, and you want to cancel some of its 1's coefficients by adding a line further down the triangle, you will create at as many new 1 on columns further right.

Formally, with <span class="math">iC_2j[/spoiler] the modulo <span class="math">2[/spoiler] equivalent in <span class="math">\{0,1\}[/spoiler] of <span class="math">iCj[/spoiler],
For <span class="math">i_2\geq i_1\geq 1[/spoiler], if <span class="math">k[/spoiler] is the number of <span class="math">j\in\{1,\dots,i_1\}[/spoiler] such that <span class="math">i_1C_2j=i_2C_2j=1[/spoiler], and <span class="math">k'[/spoiler] is the number of <span class="math">j'\in\{i_1+1,\dots,i_2\}[/spoiler] such that <span class="math">i_2C_2j'=1[/spoiler], then <span class="math">k'\geq k[/spoiler].

If we can prove this, we get quite close to the answer.

>>4188148
http://ecademy.agnesscott.edu/~lriddle/ifs/siertri/Pascalmath.htm

to the people who are good at the putnam questions:

how much mathematical background do you have?

>>4188163
Not sure if I'm "good" at those since there are a lot that I wouldn't be able to solve alone (at least not without dedicating several hours of my time), but I'll answer anyway.
My knowledge of pure maths is mostly my 2 first years of university-level courses (in those French "classes prépa", where you have 12 hours of maths and 10 of physics per week with 1 maths teacher and 1 physics teacher, and a lot of supervision from them compared to university), since afterward I jumped to computer science.
A few years later, I'm better at solving problems than I was back then (since it's more or less my job as a PhD student), but I haven't really studied many new pure maths fields (only a few applied maths fields related to computer science), so my knowledge is kinda limited compared to, say, a MS student in maths.

>>4188189

>>4188211
Yeah, I guess. 5/2? Aiming at which school(s)?

>>4188212
nope, 3/2.
Mostly reparing for X/ENS, maybe les Ponts too. But I'd take anything, really.$
Also considering EPFL as I was already interested in it, and I could manage to get enrolled in Mcgill at first, so I might want to get there too.

I haven't been much help in these threads the past few times, but I went to the Canada/USA mathcamp (mathcamp.org), which takes about 100 people, by examination, from 8th grade through the end of high school, and then I did a math undergrad, and I scored 31 or 32 (forgot) on the Putnam in 2008, and 21 in 2007.

>>4188222
Oh, I went to Mathcamp a few times, but not every year. That's just when they take students.

ITT: Nerd faggots

/fit/ here.

>>4188765
/b/ reporting in. GTFO faggots.

>>4188765
u jelly?

If you haven't mastered calculus by 15, might as well just grab the frying pan and head on down to McDonalds.

>>4188765
You are not /fit/, you're a faggot who's visited /fit/ a few times
>>4188876
You are not /b/, you're just a faggot...wait, alright, you are /b/ then.

why the fuck is this thread still here??

>>4188942
It's called a "Sticky". You can read about them here: lemonparty.org

>>4188942
because it's a sticky

>>4188943
i know, i just dont see why.
mods wanted /hm/ help?

>>4188946
Shut the fuck up, EK. Just because something isn't relevant to your particular interests doesn't mean it isn't worthwhile. We like these threads.

>>4188942

Ok you retarded zebra fucking piece of shit attention whore, it's fun. There's a daily maths question for people to have a go at solving together on the board. You probably can't understand shit because you're a retarded woman. Go learn a real subject.

>>4188960
lol, u seem mad.
and i didnt realise the question changed, i thought this had been the same one from about a week ago.

>>4188961
lol, madfags out in force his evening.

>>4188946
Go to hell, EK. math.harvard.edu/putnam has a problem every day, and they're fun challenges, and we're solving them, because they're fun. You can't do them.

>>4188966
>I didn't realize the question had changed
wow, oblivious much?

Shocker the attention whore returns. Ignore it, gentleman. This is consistently the best thread on /sci/.

>>4188995
>This is consistently a clusterfuck of incompetence and half-assed, critically flawed "solutions"

ftfy

What don't you understand in that picture?

>>4189001
And? Like I said, still the best thing on /sci/.

Also at least people are actually working on math problems in here, instead of vaguely implying superior math skills while shitposting. How are people supposed to learn if they don't try problems that are challenging, ones for which they can't just shit out an obvious answer to?

In conclusion, you're a fag.

>>4189007
Agreed!

>>4188189
>>4188211
How many are we, seriously? Ex-prépa here.

I don't think I understood this part of the problem:

For i - 0, 1, 2, ...

I'm reading "for i minus 0, 1, 2, ..."

Can someone enlighten me?

>>4189123
Transcription error, I think. From the rest of the problem, it should be an "=".

Can we be lazy and go for some kind of induction?

We have n distinct integers 0 <= i_1 < ... < i_n.

To each of these we associate

Qi = (1+x)^i = (iC0)*1^i*y^0 + (iC1)*1^(i-1)*y^1 + ... + (iCi)*1^0*y^i

By the binomial theorem.

We want to show that the number of odd terms in the polynomial Q_i1 is always <= those in the sum Q_i1 + Q_i2 + ... + Q_in ...

For n = 1, the result holds trivially since:

o(Q_i1) >= o(Q_i1)

If we assume the result holds for n integers, then...

We know that given n+1 integers 0 <= i_1 < i_2 < ... < i_(n+1)

we have the n equations:

o(Q_i1 + Q_i2 + ... Q_in) >= o(Q_i1)
o(Q_i1 + Q_i3 + ... + Q_in + Q_i(n+1)) >= o(Q_i1)
...
o(Q_i1 + Q_i2 + Q_i4 + ... + Q_i(n+1)) >= o(Q_i1)

Summing over all n equations gives that:

n*o(Q_i1) <= sum of all the mess above.

Then we need to show that one of the inequalities of the form: (must hold)
o(Q_i1 + ... Q_in+1) >= o(Q_i1 + Q_i3 + ... + Q_in+1)

It is a simple observation that

|o(Q_i1 + ... + Q_i(n+1)) - o(Q_i1 + ... Q_i(n+1)| <= i_2

Eh, this is tough... I feel I could get close to a solution for this. Better than that geometry problem.

There's something in the air

bump