/sci/ - Science & Math

>implying first post

OK, here's the solution I got.
Don't read if you want to solve it yourself.

1) Since we're concerned only with parity of the result, we can consider all number modulo 2. That is, all the <span class="math">a_j, b_j, c_j[/spoiler] and <span class="math">r, s, t[/spoiler] are now either 0 or 1 (you can think that a number turns into 0 if it's even and into 1 if it's odd; that way the parities of sums and products are conserved, and that's all we need).
2) When we take (1) into account, we can see that there can be only 7 possible different combinations of <span class="math">a_j, b_j, c_j[/spoiler]: 001, 010, 011, 100, 101, 110, 111 (it's natural to denote them with number <span class="math">k[/spoiler] spanning from 1 to 7); we don't have 000, since at least one of three numbers is odd (i.e. 1 in our representation). Similarly, we can have the same 7 combinations for <span class="math">r, s, t[/spoiler] (8, really, but 000 always gives us 0 and we can disregard it).
3) A simple inspection shows that for each combination of <span class="math">a_j, b_j, c_j[/spoiler] 4 out of 7 combinations of <span class="math">r, s, t[/spoiler] give 1, and the other 3 give 0.
4) Now, let's for each <span class="math">k[/spoiler]'th combination (<span class="math">k=1..7[/spoiler]) of <span class="math">r, s, t[/spoiler] find the number <span class="math">n_{k}[/spoiler] of triplets <span class="math">a_j, b_j, c_j[/spoiler] that give us odd result. Since from (3) each triplet gives odd sum for 4 different combinations, we have <span class="math">\sum_{k=1}^{7}n_{k}=4N[/spoiler]. From this it obviously follows that they can't all be less than <span class="math">4N/7[/spoiler] (otherwise the sum would definitely be less than <span class="math">N[/spoiler].

>>4623881

Not enough information given.

>>4624167

Either you dun' goofed, or the question is worded incorrectly. It does not say to show there are different rst for each abc. If that was true, we could just select our own rst each time to get odd 100% of the time.

>>4625024
Nope. You just don't understand the problem (or the solution).

>>4625211

Obviously. Care to clarify the problem then?

>Assume for each j, at least one of ajbjcj is odd.

Ok, so it could be that just one is odd for all j, exactly two are odd for all j, exactly three are odd for all j, or it's different for each j.

>Show that there exist integers r, s, t such that raj+sbj+tcj is odd for at least 4N7 values of j.

If it's exactly one or three each time, just let r s and t be all odd and the sum will always be odd. Otherwise, there is simply not enough information. If exactly two are odd each time, there's no way to tell which two, and so we don't know how to select r s and t. If a differing amount of aj, bj, and cj are odd for each j, there is even less information.

>>4625343
For any j different number of numbers can be odd (provided that at least one of them is odd).
You don't seem to understand the problem. It's not "name r,s,t such that for every collection of N triples at least 4N/7 combination r*aj+s*bj+t*cj give odd result". That is clearly impossible, since if I know r, s and t, I can always engineer a collection that won't give any odd results.
The problem is more like "show that for every collection of triples there're 3 numbers r,s,t such that at least 4N/7 combination r*aj+s*bj+t*cj give odd result". That is, r,s,t are the same for all triples in the collection (you can't adjust them for each triple, as you said in >>4625024), but they can be different for different collections of N triples. The difference between this formulation and the first one is that you can assume you know all aj, bj, cj in advance, before choosing r, s, t.

>>4625366

Ok, thanks friend.

there exist integers r, s, t such that raj+sbj+tcj is odd for at least 4N7 values of j, 1jN

Why does it not suffice to show that:
there are 7 possible combinations for a,b,c for all j.

If r,s,t are all odd, 4/7 combinations will be odd for every j (this is easily seen by simply multiplying through).

Show that <span class="math">\frac{gcd(m,n)}{n} nCm[/spoiler] is an integer for all <span class="math"> n \geq m \geq 1[/spoiler].

Basically the idea is that for any maximal prime power factor of n, the multiplicity of it as a factor of (n-1)! minus as a factor of m! (n-m)! is bounded below by the multiplicity in GCD(m,n).

>>4626498
I mean other way around.

Let p be a prime, and let p^k be the largest power of p in n, and let p^j be the largest power of p in m.
If p^1 divides m and n, then the number of multiples of p in between 1 and n is equal to the number of multiples of p in between 1 and m, plus the number of multiples of p in between 1 and n - m, because the multiples of p between m+1 and n line up with the multiples of p between 1 and n-m. This applies for every power of p except for ones that divide n but not m; in those cases, there's one more between 1 and n than between 1 and m and 1 and n-m combined. In these cases, each power contributes one more factor of p to n! than to m!*(n-m)!, which compensates for dividing by all the factors of p in n that aren't in m and therefore aren't in GCD(m,n)

>>4626562
The reason the number of multiples of p between 1 and n matters is that the multiplicity of p as a factor of n! is one for every multiple of p, and one more for every multiple of p^2, and one more for every multiple of p^3, and so on. The multiplicity of p in n! is actually <span class="math">\sum_{i=1} \lfloor \frac {n}{p^i} \rfloor[/spoiler]

Do you just eventually learn how to do these problems by studying math in general? Or is there a more specific way to work your way up to understanding them? They're always worded so confusingly in my opinion but I think it's just because I don't completely grasp all the notation that's used.

>>4626957
It's pretty normal phrasing for mathematics.