/sci/ - Science & Math

>>4380004
Oh, fuck. nevermind. I forgot about subtracting 1 from <span class="math">a_n[/spoiler]. duh.

>>4379995 <span class="math">[/spoiler]
If <span class="math">a_n = d_n\alpha_n[/spoiler] and <span class="math">b_n = d_n\beta_n[/spoiler] then

<span class="math">a_{n+1} = 3a_n + 4b_n = d_n(3\alpha_n + 4\beta_n)[/spoiler], and
<span class="math">b_{n+1} = 2a_n + 3b_n = d_n(2\alpha_n + 3\beta_n).[/spoiler]

So <span class="math">d_n|d_{n+1}[/spoiler], which implies <span class="math">d_n\leq d_{n+1}[/spoiler]

>>4379989
Wait, hold on. It's immediately true!

>>4379977
Doh, I really don't know what I was thinking in >>4379948 . You're of course right: showing <span class="math">(d_n)[/spoiler] is nondecreasing is sufficient. But I have a hunch that won't be much easier to prove.

>>4379937
I'm not so sure, because it could still conceivably be the case that the sequence <span class="math">d_{2n+1}[/spoiler] is constant.

>>4379816
I assume you're trolling.
But if not, I'd be interested to see where you can find the solution I gave to the problem that TN5 linked to in >>4379766 .

It's true, I did look ahead in the MAA Putnam archive a few days ago. (Hey, I couldn't help it! I've got Putnam Fever.) But if I ever solve a problem beforehand, I wouldn't bother posting a solution — at least not before others do. To do so would pointlessly ruin the thread for everyone else.

Anyway, the MAA Putnam archive doesn't have solutions before 1995. But I'm guessing that starting in three days, these threads might get ruined a lot more frequently.

>>4379896
That's very nice! But it doesn't completely prove the statement. For example, it doesn't show that <span class="math">d_{2n+1}\to\infty[/spoiler] as <span class="math">n\to\infty[/spoiler].

>>4379766
Sorry, I got the wrong impression.

>>4379742
TN5 is the moderator who posts these threads. If she/he is in here: you should change the (2,2) entry to a 3 in the original post.

>>4379718
It should be a three:
http://amc.maa.org/a-activities/a7-problems/putnam/-pdf/1994.pdf


I haven't worked on it any more than the observation in >>4379692
I'm guessing we can solve this one in no time.

>>4379694
I would have nothing to gain. But I realize that hasn't stopped others, so you're free to suspect it.

>>4379692
Forget this. I thought the (2,2) entry was a three. I could have sworn it was — I checked out this problem a few days ago.

Easy proof by induction that <span class="math">A^n[/spoiler] has the form <div class="math">A^n= {a_n\ \ b_n \choose 2b_n\ \;a_n }.</div> That's gotta be worth something.

Not sure what you mean by "most difficult". There are very smart mathematicians working in all the major fields. It's not as if there are set tasks for each day and the K-theorists always finish their tasks early because they're easy.

But there are fields that seem to take longer for grad students to get up to the research level because there is just so much background material. Combinatorics is definitely not one of them.

Nonlinear PDE would be a good example (it also happens to be my field, so perhaps I'm biased).

>>4375571
Nope.
http://en.wikipedia.org/wiki/Likelihood_function

Assuming that each <span class="math">n_j[/spoiler] is randomly chosen from <span class="math">\mathbb{Z}[/spoiler], and assuming that all integers are equally likely to be chosen:

For any given <span class="math">c\in\mathbb{Z}[/spoiler] and <span class="math">m\in\mathbb{Z}^+[/spoiler], the probability that <span class="math">n_{m+1}=c[/spoiler] is clearly zero.

I suspect you rather meant to ask this:
Given any integer <span class="math">c[/spoiler], what is the probability that <span class="math">n_m=c[/spoiler] for *some* <span class="math">m\in\mathbb{Z}^+[/spoiler].

That's the more interesting question.

http://en.wikipedia.org/wiki/Lambert_W_function

Thanks for the jpg, OP. It made me smile.


It really depends on your current level. I say check out the Amazon pages for those books and look at the similar titles. Read reviews. You should get a good idea of what books are helpful.

I remember when I was a 1st year college student, I was fond of the Wohascum County Problem Book.

In high school, I bought books of USAMO and IMO problems and solutions.

>>4373265
I should point out that you have so far only shown that <span class="math">c<243/8[/spoiler] is necessary. Sufficiency remains.

The way they grade the Putnam, that's probably 2/10 or 3/10.


>>4373285
I know I should resist feeding the trolls, but just in case you are serious: You should use the notation that is most effective in the given situation. In this case, Leibniz notation would have been cumbersome.

>>4372384
>>4372506
Both are very nice solutions. Here is a slightly different take on the first: use Rolle's theorem twice on <div class="math">x^4 + 9x^3 + cx^2 + ax + b - (\alpha x + \beta)</div> to show that <span class="math">c<243/8[/spoiler] is a necessary condition. Then observe that this condition amounts to the existence of exactly two distinct inflection points, <span class="math">(x_1,y_1), (x_2,y_2)[/spoiler], <span class="math">x_1<x_2[/spoiler]. Consider the line connecting these two points.

Since any monic fourth degree polynomial is convex in the intervals <span class="math">(-\infty,-M)[/spoiler] and <span class="math">(M,\infty)[/spoiler] for <span class="math">M[/spoiler] sufficiently large, the polynomial must be strictly concave between the two inflection points and strictly convex everywhere else.

[Here I go a little bit overboard with the rigor.]
If <span class="math">L(x) = \alpha x + \beta[/spoiler] is the line and <span class="math">p(x)[/spoiler] is the given quartic, then by the mean value theorem, at some argument <span class="math">\xi\in(x_1,x_2)[/spoiler], the slope <span class="math">p'(\xi)=\alpha[/spoiler]. Since <span class="math">p'[/spoiler] is strictly decreasing between the inflection points, it is clear that <span class="math">p'(x_2) < \alpha < p'(x_1)[/spoiler]. By the continuity of <span class="math">p'[/spoiler], it follows that there exists some <span class="math">\epsilon>0[/spoiler] for which <span class="math">p(x)<L(x)[/spoiler] in <span class="math">(x_1-\epsilon,x_1)[/spoiler] and <span class="math">p(x)<L(x)[/spoiler] in <span class="math">(x_2,x_2+\epsilon)[/spoiler].

But <span class="math">\lim_{x\to\pm\infty}p(x) - L(x)=+\infty[/spoiler]. So by the intermediate value theorem, the line must intersect the curve at some point in the interval <span class="math">(-\infty,x_1)[/spoiler] and at some point in the interval <span class="math">(x_2,\infty)[/spoiler].

>>4367185
lol. I actually realized that when I responded the first time. But then I forgot an hour later. Clearly, it's way past my bedtime.

So the problem has been solved. Excellent.

Good night, all.

>>4366885
Actually, upon further reflection, I'm not so sure about the last part. Suppose (0,1,1,1,1,1,1,1,1,1) and (1,0,1,1,1,1,1,1,1,1) both correspond to compositions that do map <span class="math">A\to A[/spoiler]. Then the corresponding "does not map <span class="math">A\to A[/spoiler]" sequence is the same for both of them: (0,0,1,1,1,1,1,1,1,1) . So we don't get that 1-1 correspondence between "does map" sequences and "does not map" sequences.

I'll think about this more tomorrow (if I have time). I think we're close.

>>4367047
>Therefore, you cannot possibly have all of the <span class="math">f_i[/spoiler] fixing a nonempty set <span class="math">A[/spoiler].
Well, unless <span class="math">A=\mathbb{Z}[/spoiler], of course. But <span class="math">\mathbb{Z}[/spoiler] isn't finite, so we needn't worry about it.

>>4366885
>(There is at least one such i by transitivity.)
It took me a bit of time, but I now see what you mean. The condition
"for every <span class="math">n\in\mathbb{Z}[/spoiler], some chain of compositions of the <span class="math">f_i[/spoiler] maps <span class="math">0\mapsto n[/spoiler]"
necessitates that the group generated by the <span class="math">f_i[/spoiler] act transitively on <span class="math">\mathbb{Z}[/spoiler]. Therefore, you cannot possibly have all of the <span class="math">f_i[/spoiler] fixing a nonempty set <span class="math">A[/spoiler].

Wow, that's it. The rest of your proof is correct. Very nice.

>>4366872
Are you the poster of >>4366578 ?

I'm confused by what you're saying here. <span class="math">(\mathbb{Z}/2\mathbb{Z})^{10}[/spoiler] is supposed to act on <span class="math">\mathbb{Z}[/spoiler], right? This would make sense in the context of >>4366578
But you now seem to have the group acting on the set <span class="math">S[/spoiler] of 1024 functions of the form <span class="math">f_1^{e_1}\circ\cdots\circ f_{10}^{e_{10}}[/spoiler].

So if you let <span class="math">X=\{F\in S\,:\, F(A)=A\}[/spoiler], we may consider the the subgroup <span class="math">H\leq (\mathbb{Z}/2\mathbb{Z})^{10}[/spoiler] that fixes <span class="math">X[/spoiler]. The order <span class="math">|H|[/spoiler] divides 1024. But that doesn't tell us anything about the size of <span class="math">X[/spoiler].

I don't remember much about this orbit-stabilizer business. Is there a way we can use this construction to get a hold of the size of <span class="math">X[/spoiler]? Perhaps Burnside's Counting Lemma?