/sci/ - Science & Math

[Anonymous No.4411090]

Putnam/Olympiad problem of the day from
http://math.harvard.edu/putnam/

[Anonymous No.4411120]

I fail to see the practical importance of such an inquiry.

[Anonymous No.4411126]

What's this trivial shit doing in my putnam thread?

>implying we cannot count single digit numbers

[TN5 !/sci/TN5.. No.4411172]

If <span class="math">\pi[/spoiler] contains a part <span class="math">\{a,b,c,d,...\}[/spoiler] of cardinality <span class="math">>=4[/spoiler], then consider the size of the parts <span class="math">p_a,p_b,p_c,p_d[/spoiler] of <span class="math">\pi'[/spoiler] that contain respectively <span class="math">a,b,c,d[/spoiler]. If two of these parts have the same size, we're done. Otherwise, their sizes are different, which is impossible because it would mean that they are of sizes at least 1,2,3 and 4, which totals to 10>9.

Thus let's check what happens when <span class="math">\pi[/spoiler] and <span class="math">\pi'[/spoiler] only contains parts of cardinality at most <span class="math">3[/spoiler]. Consider the function <span class="math">x\mapsto f(x)=(\pi(x),\pi'(x))[/spoiler]. This function has 9 possible outputs:
(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3
,2),(3,3)
If there is <span class="math">x\neq y[/spoiler] such that <span class="math">f(x)=f(y)[/spoiler], then we're done. Otherwise, each of the 9 values of the domain is mapped to a different value in the range of <span class="math">f[/spoiler]: the whole range is reached. That would mean that there are exactly <span class="math">3[/spoiler] elements that are in a parts of size 2 in <span class="math">\pi[/spoiler], which is impossible (that number has to be even).

Probably not the best way to do it, but whatever...

[Anonymous No.4411215]

>>4411172
Easier to see is that no partition can have less than 4 elements that have the same pi(x). The best you can do is something like (a)(b)(c)(d e)(f g h) but that is only 8 elements. Then use that first fact.

[Anonymous No.4411275]

>>4411215
>>4411172
Actually that first part needs clarifying, though it should be obvious. If pi(a) = pi(b) = pi(c) = pi(d), then the elements a,b,c,d must go to different size subsets in pi'. And as had been said, the best you can do is 1,2,3,4. Obviously if you have a subset of size 4+, then there are 4 elements with the same pi(x). But it's also true for something like (a b)(c d) ...

[Anonymous No.4411405]

Define the following function on integers and partitions: #(n, p) is the number of parts in p that have size n. We can use this function to define |p| as the maximum n * #(n, p).
Note that if p = 9, then |p| >= 4. (Assume that |p| < 4, then there are at most 3 parts of size 1, 1 part of size 2, 1 part of size 3, none larger, which doesn't add up to 9, hence |p| >= 4).
Furthermore, we define ||p||, which is the maximum n * #(n, p) that does not equal the n for |p| (so the second largest n).
Note that if p = 9, and |p| = 4, then ||p|| >= 3. (Assume that ||p|| < 3 then the remaining 5 elements must be cut up in 2 parts of 1, and 1 part of 2, which doesn't add up to 5, hence ||p|| >= 3.)
If there are x and y, such that x and y in |pi| and |pi'|, then trivially, such x and y have pi(x)=pi(y) and pi'(x)=pi'(y). We assume, wlog, that y is not in |pi'| (but in |pi|). There are at most 5 elements not in |pi'|, and at least three of them are in ||pi'||. Since there 3 choices for x that are in |pi|, at least one of them must be in ||pi'||. Hence, that also satisfies pi(x) = pi(y) (both in |pi|) and pi'(x) = pi'(y) (both in ||pi'|| this time).
QED

[Anonymous No.4411733]

Guys if I have scalar multiplication defined such that cA = is cA^t (in the second case c is applied to each element in the matrix) is this a vector space?

[Anonymous No.4411866]

>>4411733
No
1A =A^t ≠ A
for some A

[trl No.4412220]

Sorry for the bad format -- I will have to go relearn LaTex again.

First of all notice it is not true for the set {1,2,3,4,5,6,7,8,9,10}
\pi = {{1},{2,3},{4,5,6},{7,8,9,10}} and \pi ' ={{7},{4,8},{2,5,9},{1,3,6,10}}
the partitions from \pi intersect ones from \pi ' in only one number.

so back to the case {1,2,3,4,5,6,7,8,9}

we can simplify by thinking of the partitions you get by looking at the
inverse of \pi and \pi '

ie P = { inverse \pi (x) for x = 1,2,3,4,5,6,7,8,9}
and P' similarly with \pi '

So x, y exist iff there are parts in P and P' that intersect with at least two
elements

P is related to \pi as follows: all the parts of \pi of a certain size are combined

eg if \pi = {{1},{2,3},{4,5,6},{7,8,9}} then P = {{1},{2,3}, {4,5,6,7,8,9}} (the two parts of size 3
are combined)

The partition P will have size 9a + 8b + 7c + 6d + 5e + 4f + 3g + 2h + 1i
where the letter is the number of \pi parts of that size.

Lets just enumerate the possibilities:
9*1
8*1 + 1*1
7*1 + 2*1
6*1 + 3*1
6*1 + 2*1 + 1*1
5*1 + 4*1
5*1 + 3*1 + 1*1
4*1 + 3*1 + 2*1
4*2 + 1*1
3*2 + 2*1 + 1*1
3*3

So we see that P (and P') has at most 3 parts and at least one part has more than 4 elements

If you take that large part from P with 4 or more and intersect it with P' (which has at most 3
parts) at least one of those intersections has 2 or more

[BrodyMontana No.4412524]

can you solve these in boolean expression form?

(a) The statement is true if and only if x and y are both positive unless y is greater than twice x.

(b) The statement is true if and only if x is between 90 and 100, inclusive, and y is
at least 12.

(c) The statement is true if and only if the product of x and y is less than the square of y but y is in the range 0 to 100

[Anonymous No.4412749]

These questions always make me feel even more retarded than i thought i was before


why...why cant i do math like this

[Anonymous No.4412802]

This is now a thread about animals doing people things.

[Anonymous No.4413017]

[Anonymous No.4413028]

>pi(x)


Putnam in charge of notation.

[Anonymous No.4413059]

>>4413028
They ain't got nothin' on physicists.

[Anonymous No.4413069]

>>4413028
Wait till you see homotopy groups

[Anonymous No.4413195]

>>4413059
Okay, that would frustrate me a little.

[Anonymous No.4413390]

So what math is this? i haven't taken anything beyond calc 3.

[Anonymous No.4413603]

>>4413390
discrete math

[Anonymous No.4413806]

>>4413028
<span class="math">\pi[/spoiler] is pretty standard for permutations. Hadn't seen it for partitions yet though, but that didn't really shock me. In discrete maths, you know <span class="math">\pi[/spoiler] won't be the number <span class="math">\pi[/spoiler], so there is no possible confusion. >>4413059 is a whole other story, though...

[Anonymous No.4413823]

>>4413806
Also, probability distributions are sometimes denoted by <span class="math">\pi[/spoiler] (I'm thinking ergodic processes / Markov chains theory), as well as probability transition matrices (well, probability transition matrices are just a generalized view of permutations).

[Anonymous No.4414051]

Has any of you guys ever heard about negative dimensions?

[Anonymous No.4414114]

>>4414051
The null set has dimension of negative one. Other negative dimensions are pretty fucking cool too.