DAILY MATHS CHALLENGE THREAD

File: 2016-12-31 16.06.23.png (157KB, 923x707px) Image search: [Google]

157KB, 923x707px

And here's problem numer 2.

Cool, I remember the good days when we had those regularly. Keep it up. One question and one remark:
*) Why do you post the first one on Dec. 31 and not Jan. 1? Sure, I'm slightly autistic but this bugs me a little.
*) Can you try to make them not all just combinatorics? It's a little more work, but (if you're already posting more questions per thread, like here) posting problems of varying difficulty from another math field would be more interesting as those "one-off problems, where you use some trick you never use again for something else"

File: Screen Shot 2016-12-31 at 15.57.34.png (181KB, 1298x716px) Image search: [Google]

181KB, 1298x716px

>>8572845
okay, but now to start thinking about it, I first went to Mathematica as I know it has a support for all the cellular automata shizzle (of course, Wolfram is among original automata meme masters), at least for making some pictures. If someone else is motivated, I haven't used this before and haven't tried enough to figure out how you specify change rules yet.
Btw. this is just to makes blinking gifs and gain some intuition for this kind of problems.

File: 3.png (26KB, 866x191px) Image search: [Google]

26KB, 866x191px

>>8572845
I started this thread because I was bored. Didn't realize I should wait one more day, sorry OCD people.
I definitely will be taking it easy with the Combinatorics from now on, I chose those 2 problems because the first is relatively easy and for the second I have a proof based on constructing an algorithm for operating the switches and proving it works. I guess I wanted to attract some of the CompSci people here, too. I'll be focusing on Algebra and Calculus from now on, and maybe some Number Theory sometimes. Sorry, I can't for the life of me solve Geometry problems so I'll be avoiding those.
Here's a nice Calculus problem, the last I'll be posting in this thread today.
>>8572858
Nice initiative, but I think you're overcomplicating things a bit. Just grab a piece of paper and see what happens for n up to 5 or 6. I'm open to discussions and I'll be posting solutions if there's enough interest but no one manages to solve the problems (which I highly doubt, except maybe for the second one)

>>8572874
>but I think you're overcomplicating things a bit.
=>
>>8572858
>Btw. this is just to makes blinking gifs and gain some intuition for this kind of problems.

>>8572874
>Sorry, I can't for the life of me solve Geometry problems so I'll be avoiding those.

So what you're telling me is that you don't actually want to learn anything, you just want to brag about the problems you've been able to solve.

>>8572878
I'm saying that I have no interest in solving Geometry problems or learning about this subject. I'm also saying that I am not qualified to judge the difficulty of Geometry problems and select proper ones for /sci/. I'm also saying that I believe very few, if any, people on this board are interested in synthetic Geometry problems.
That being said, if anyone has suggestions for problems (Geometry included), you are very much welcome to post them here. The best way to judge problems is by letting the community attempt to solve them. In no way do I wish to be the sole author of those threads.
If you're not interested in those threads sage, report, or just ignore them. Several people have voiced their strong approval to the idea of those threads to I will be continuing.
Now, can we get back to the actual maths problems, please?

The problem is still worded strangely

>>8572885
Which one, anon? I will try to clarify any questions you have.

>>8572886
Forget it, I'm a brainlet

File: Hint1.jpg (4MB, 3014x2115px) Image search: [Google]

4MB, 3014x2115px

Here's a small hint on problem 1 for anyone stuck on it.

>>8572917
The problem is the pattern gets a little more complicated. For instance n = 8 is

1000 0000
1100 0000
0110 0000
1111 0000
0001 1000
0011 1100
0110 0110
1111 1111
0000 0000

I'm not sure how to generalize it, but I'm a brainlet.

>>8572823

If n is a power of two it will always go dark (induction). If n = 2^k + r, with r>0 and k the biggest integer where n > 2^k, then it will never go dark.

Did I get it right?

>>8573027

Didn't read the hint, btw.

>>8573027
yeah, that's right. But it's a kinda difficult to prove that it holds for all n=2^k+r. Can you just find an infinite number of such numbers for which it's easy to prove?
>>8573024
what do you notice in step 5 and onwards? the pattern has a certain property you can control and use.

>>8572874

a) No, because that'd mean there's a Cauchy sequence that's divergent, and that's impossible (in R with the usual metric).

b) Take f(n) = n and the above result for a counterexample.

I'm sure there's something I'm not seeing here, because if not then asking b) makes no sense.

>>8573051

n = 2^k + 1, after 2^k +1 steps, it'll return to the second step of the sequence.

>>8573055
Nope, you're wrong. Check the definition of a Cauchy sequence. This problem isn't super difficult but it tests some fine details about one's understanding of the definitions of convergence and Cauchy sequences.
>>8573057
yeah, that's right. One small detail though, after [math] 2^k [/math] steps it mirrors the initial state, and it only repeats after [math] 2^{k+1}[/math] steps (I'm not counting the initial state as a "step").

>>8573065
Yeah, I just wrote it down and it came to mind, the thing is that in the Cauchy sequence definition n0 is only determined by epsilon, but here it can also depend on k. I can't think of an example of such a sequence, but that difference should be enough.

I feel like b) doesn't hold, but I can't see why yet. I'll try to proof that an must be convergent, see you in a bit.

Also, synthetic geometry is pretty comfy.

>>8573057
How can you prove that this pattern holds though?

>>8572874

For (a) just take a_n = 1/1 + 1/2 + ... + 1/n

This diverges since its partial sums of the harmonic series. But for a fixed k, 1/(n+1) + 1/(n+2) + ... + 1/(n+k) will only get smaller.

>>8573090
yeah, that's right.
I'll tell you from now, part b is pretty though. You're right that it doesn't hold, but the proof is a bit crazy.
>>8573087
OP here, I'll answer in place of the dude you replied to. First you prove (inductively) that for [math] n=2^k [/math] the sequence always turns off. Then you consider [math]n=2^k+1 [/math] and for the first [math] 2^k[/math] steps it behaves like [math] P_n [/math], which means that after [math] 2^k [/math] steps the first [math] 2^k [/math] cells are all lit and the last one isn't; this means that on the next step the only cell that is lit is the last one. This is the exact same pattern that you started with, only mirrored. Thus the pattern will repeat and never turn off completely.

>>8573090
Fuck me sideways with a slide ruler, how didn't I think of that.

>>8573098
You sure? I just said that, since an is divergent, you can define an f so that a(n+f(n)) > an for all n. It's really wishy washy, but it works for me, and I don't see any problems with it (apart from being so unprecise).

>>8573107
well... that doesn't prove anything. Yes, you can define f in such a way, but that only means that [math] a_{n+f(n)}-a_n \geq 0 [/math]. Why would the limit then have to be 0? Or, on the contrary, why couldn't it be 0? Doesn't work, sorry pal. Will post the proof here later if you want.

>>8573107
>you can define an f so that a(n+f(n)) > an
No, you can't do this in general.
For example consider the sequence
[eqn]a_n = (-1)^n [/eqn]
You can't find such an f for even values of n.

>>8572823
a) Let's prove by induction that whenever n is a power of 2, L_n stays switched off, until a point where all lights are switched on:
It works for n=2. Assume it's true for n=2^k.
Now consider the case n=2^{k+1}. The first 2^k lamps behave as they would if there weren't lamps to their right until L_{2^k} is switched on.
(now this would require another induction, to justify that the 2^k lamps to the right stay off and in particular L_{2^k} and L_{2^k +1} always agree).
By induction hypothesis, we then reach a point where the first 2^k lamps are on, and the last 2^k lamps are off. At the next step, we get to the configuration 0 ... 1 1 ... 0.
Because of the symmetry, it is easy to prove by induction that L_2^k and L_{2^k +1} agree from then on. Hence, we can assume these two halves behave like two independent copies of the n=2^k configuration, which arrive at the same time at the configuration where all their lamps are switched on. It also follows that L_{2^{k+1}} stays off until the step where all lights are on, since it was off until we arrived at the 0... 1 1... 0 stage, and since the last half behaves like the 2^k configuration, the induction hypothesis tells us that it stays off until all lights are on in the rightmost half.

I hope I made myself clear, English is not my native language :/

>>8572874
a) pick a_n = ln(n)
b) Not possible. Assume [math](a_n)[/math] diverges. Then, since (a_n) is not cauchy, there exists [math]\epsilon > 0[/math] and increasing [math]\phi, \psi: \mathbb N^* \to \mathbb N^*[/math] such that [math]\forall n \in \mathbb N, |a_{\phi(n)} - a_{\psi(n)}| \ge \epsilon[/math].
Hence, either [math](a_{\psi(n)} - a_n)[/math] or [math](a_{\phi(n)} - a_n)[/math] doesn't converge to 0.

>>8573122
But that's not divergent.

>>8573117
Yeah, I'm not a really clever guy. I'm still not sure whether to proof the limit is not zero or that an is convergent, though.

Also, did you derive any kind of pleasure out of me being this wrong?

>>8573129
That's really slick, anon. How did you come up with that modification of the definition of a Cauchy sequence?

>>8573140
its just a negation of the statement

>>8573140
Well I knew I needed to introduce functions somehow. And not being Cauchy is exactly saying that there is some [math]\epsilon >0 [/math] such that [math]\forall N \ge 0 \exists m(N),n(N) \ge 0, |a_{m(N)} - a_{n(N)}|[/math].
Then, with a little induction, you can find the appropriate [math]\phi[/math] and [math]\psi[/math]

>>8573136
A sequence is said to be divergent if it is not convergent, i.e. it does not go to a limit that is a real number. A sequence is divergent if it either doesn't have a limit or the limit is [math] \infty [/math] or [math] -\infty [/math]. So it's correct.
I didn't derive any pleasure from you being wrong lol. In fact, I was wrong too when I agreed about the existence of a function f.
>>8573129
Yeah, I agree on the proof of point (a) of the first problem. What about b, though? It isn't much harder.
For the calculus problem: first, for (a), you used the example [math] a_n=\ln n [/math]. Some other anon used the harmonic series [math] b_n=\sum_{i=1}^n \frac{1}{i} [/math] I just want to point out that those both work because they get ever closer as n goes to infinity. That is, [math] a_n-b_n [/math] converges.
Now for point (b). Can you prove that there must exist [math] \phi , \psi [/math]? I normally define their values inductively using the negation of Cauchy. Also, you're looking for the convergence of [math] (a_{n+\phi (n)}-a_n) , not (a_{\phi (n)}-a_n}. Your proof has to be adapted a little bit but yes, you have the main idea down. Congrats! How hard was the problem to you?

>>8573159

Thanks anon.

>>8573165

I always forget about that little detail. I always just use not convergent to include the case where the limit doesn't exist and divergent when it's infinite.

>>8573129
Well done.

I'm new to doing proofs and I suck at it. Is it possible to get good at them through practice or is it just down to raw talent?

>>8573188

Different mathematician here, but it is definitely something you can become good at with practice.

File: JohnvonNeumann-LosAlamos.gif (281KB, 490x639px) Image search: [Google]

281KB, 490x639px

>>8573188

A lot of it is just practice, and you can get really far by working on it, though there will always be people who would have done it much faster and much better than any of us ever could (pic very much related).

I see that people have cracked the first and last problems. Anyone up to thinking about the second combinatorics one?

>>8573165
I think the answer to b) is >>8573057, I can expand his proof a little bit using what I have

For the calculus problem, I outlined the construction of phi and psi here >>8573159.
We first find functions [math]s(n), t(n)[/math] such that [math]\forall n \in \mathbb N, s(n),t(n) \ge n \wedge |a_{s(n)} - a_{t(n)}| \ge \epsilon[/math]. Then, we can define [math]\phi,\psi[/math] inductively as follows: [math]\phi(1) = s(1); \psi(1) = t(1)[/math]. Then, for each [math]n \in \mathbb N, \phi(n+1) = s(\max(\phi(n),\psi(n))+1); \psi(n+1) = t(\max(\phi(n),\psi(n))+1)[/math]
and then using the fact that phi and psi are increasing, we have [math]\forall n \in\mathbb N, \phi(n), \psi(n) \ge n[/math], hence [math]\phi[/math] and [math]\psi[/math] can both be written as [math]n \mapsto n + f(n)[/math] for some f.
Thanks ! I figured it out pretty quickly, but I'm not an undergrad :)

File: latest[1].png (23KB, 462x377px) Image search: [Google]

23KB, 462x377px

>>8573198
>von neumanlett
I see what you did there

>>8573203

I'm trying to understand how you came up with it. So:

1.- You already suspected it was false, so you worked towards that direction.

2.- You (for some reason) decided against proof by contradiction (I really try to use these ones a bit too much, not really sure why) and just went head on.

3.- You knew an was divergent, which means not Cauchy's, whose definition comes in handy in this case.

4.- You saw you needed to somehow introduce functions into the mix, so you found an equivalent formulation of Cauchy through increasing functions.

5.- ???

6.- Profit.

Did I do it right? Was this more or less what you did?

>>8573205

I don't see it.

>>8573224
Pretty much, yeah. I'm not sure why I thought it wouldn't work, but it seemed too strong to hold. I hadn't decided against proof by contradiction, it just turned out that once I had rewritten the negation of Cauchy sequence in terms of functions, it said exactly what was needed.
The hardest thing imo was to remember that divergent <-> not Cauchy, after that it went well

Here are more calculus problems, let's see some computations:
Under which condition(s) does the series [math]\displaystyle\sum (\ln n + a\ln(n+1) + b\ln(n+2))[/math] converge ?

Under which condition(s) do the integrals [math]\displaystyle \int_{\pi}^{\infty}\dfrac{dx}{x^a (\sin x)^{p/q}}[/math] and [math]\displaystyle \int_{\pi}^{\infty} \dfrac{dx}{x^a|\sin x|^b }[/math] converge ? (a,b are real and p,q are positive integers, with q odd)

File: 4.png (17KB, 919x117px) Image search: [Google]

17KB, 919x117px

>>8573254
The first problem is easy; the series is convergent iff the series [math] \sum (1+a+b) \ln n [/math] converges, which only happens for 1+a+b=0.
No idea for the second one, integrals are hard for me.
Also here's another nice problem for you guys.

>>8573254

If the integrals can't be done with residues, then god fucking damn it.

>>8573276
I agree that first problem is easy, but you didn't give the right condition (consider the case a=-1,b=0)

>>8573294
It's a very different problem, this is just asking you whether it converges, not to compute its value (which I'm not sure is even possible).
It's really about estimating, not about computational tricks

>>8573313

I'm not an engineer, so I'm not used to this... "estimating" stuff.

>>8572884
>I'm saying that I have no interest in geometry problems blah blah
Anon who cares what you have interest in or what you're qualified to judge? Select an Olympiad exam, Putnam exam, or problem-solving text and pick a geometry problem from there. You have resources where people have already made that judgement for you. If you end up selecting one which is too easy, then whatever, ignore the complaints and make a new thread tomorrow. Do you understand? You don't owe us any apology if yoh screw up, and those of us legitimately interested in these threads would forgive the occasional misstep anyways.
I propose you select a different category for each day of the week, e.g.
Monday - Number Theory
Tuesday - Algebra
Wednesday - Geometry
Thursday - Combinatorics
Friday - Analysis
If you want, I can take over since I feel that I know my resources a bit better, and I'd also be willing to set up a pastebin with end-of-the-week solutions.

>>8573254
>>8573305

a = -2, b = 1, and I think that's it.

>>8573305
FUCK I'm such a brianlet. I can't believe I made such a stupid mistake. Now I've thought about the problem properly and I'm confident there are no a, b for which the series is convergent. The convergence is equivalent to that of the series [math] (\sum_{i=1}^{n+1} (1+a+b) \ln i ) -\ln (n+1) [/math] which implies [math] 1+a+b=k \geq 0 [/math] and then we have that [math] \ln fraq {((n+1)!)^k}{n+1} [/math] must converge for some k>0 which is false, for example by the Stolz-Cesaro lemma.
>>8573321
T-thanks anon kun...
I guess I'll try. We'll have another thread tomorrow like this one and then starting on Monday I'll try to keep everything more organizes. I think that compiling all these problems together would be amazing, I'd really appreciate if you could do that.
I guess I'll just try my best to select a Geometry problem every week and try to follow the discussion here, maybe I can learn something and get better on the way, but the chances are slim.
The other field I'm afraid I could disappoint with is Calculus. I'm only in high school so my Calculus knowledge is limited (i. e. I struggle with most integrals) and they aren't normally part of olympiad curriculum so my choices are kinda limited to Putnam problems which I imagine most people here already read and attempt. I suppose I have some nice and relatively hard problems from last year (mostly about derivatives, continuity and Darboux property) but don't expect very advanced stuff from me there yet, sorry.
We'll see how this and tomorrow's threads go and then maybe do a poll to try and organize stuff. I'm definitely down to selecting (hard) Algebra, NT and Combinatorics problems and discussing them here and I think I can manage this side alone for a pretty long time.

>>8573254
>>8573305
>>8573353
sigh... i just realized that's wrong
I'll try one more time and if I can't do it tonight I'll try again tomorrow.

>>8573319
Really ? It seems like the most engineering-y thing there is. Here's an idea of how you can proceed (everything can be made rigorous):
We notice that [math]\int_{\pi}^{\infty} \frac{dx}{x^a|\sin x|^b} = \int_0^{\infty} \frac{dx}{(x+\pi)^a|\sin x|^b} \ge \int_0^{\pi}\frac{dx}{(x+\pi)^a|\sin x|^b}[/math].
Now, since [math]|\sin x| \sim x[/math] around 0+, and the integral [math]\int_0^{\pi/2}\frac{dx}{x^b}[/math] diverges for b > 1, we can imagine that it would also be the case for [math]\int_0^{\pi/2}\frac{dx}{(x+\pi)^a|\sin x|^b}[/math], and hence for the initial integral.
Then we look for inequalities in the calculus syllabus to help us confirm this intuition

>>8573336
That's right, proof ?

>>8573353
Hint, you almost had it the first time, you just didn't push hard enough

I finally got it right this time.
[math] lim_{n \to \infty } ((1+a+b) \ln n! +(a+2b) \ln n) \in \mathbb {R} \iff lim_{n \to \infty } \ln (n!)^{1+a+b}n^{a+2b} \in \mathbb {R} [/math] but the factorial is an exponential function while[math] n^{a+2b} [/math] is polynomial so in order for the limit beneath the logarithm to be neither 0 not [math] \infty [/math] both exponents need to be 0. That is, [math] 1+a+b=0, a+2b=0 \iff a=-2. b=1 [/math] which obviously are indeed solutions.

>>8573353
To clarify, when I mentioned Algebra, I meant Abstract Algebra.
Keep in mind that a daily problem thread should not be about your strengths and your weaknesses, it should be a high-level daily problem thread. Given that the board is 18+, it's safe to assume that any anons participating are pursuing an undergraduate degree or higher, meaning the topics can be more broad. Polling shouldn't be necessary, just give the core subjects their time and compile the week's problems over the weekend.
Check out the text books Problem Solving Through Problems, Putnam and Beyond (they are hosted on university sites; you can find them with a Google search, no need for piracy), any university's "Problem-Solving" or "Putnam Preparation" course webpage, and of course previous Olympiads/Putnam exams.

>>8573378

The proof is left to the reader =D (I took the series to define a function, and then calculated the derivative and in the denominator appeared (1+a+b) n^2 + (3 + 2a +b) n + 2, so I got a = -2 and b = 1 to get rid of those pesky coefficients)

And about the integrals, couldn't be the case that it converges in [0, pi] but not in [0, inf]? sin(x) has a fuckton of zeroes all over the place.

>>8573381

Where the fuck did you get that expression from, anon?

>>8573409
>The proof is left to the reader =D
Come on, that's not the point of the thread !

>>8573409
>And about the integrals, couldn't be the case that it converges in [0, pi] but not in [0, inf]? sin(x) has a fuckton of zeroes all over the place.
Oh of course, but the convergence on [0,pi] is necessary, so we already know that we need to narrow the search down to the couples (a,b) with b<1. It was also to give an idea of the tools that would need to be used in order to solve the problem

>>8573381
I see what you did there, but you'll need to explain a little bit why it does solve the initial problem (because the partial sums don't equal the thing inside the limit, although they're pretty close)

>>8573409
I replaced [math] \ln (n+1) [/math and [math] \ln (n+2) [/math] with [math] \ln n [/math] because they're about the same size and the first series is convergent iff the one I wrote is. From there I just used the properties of logarithms and the fact that any exponential function "beats" any polynomial function in the long run.
>>8573388
Oh, I was thinking more about olympiad-style Algebra. There was a thread 2 days ago (the one that inspired me to write this one) about an Algebra problem from an IMO shortlist so I thought that would be appropriate. Now that I think about it, though, you're right - Abstract Algebra would be better suited here. Again, that puts me at a disadvantage - I am only now studying Group Theory, rings and fields will come soon so I'm not much help in this area either. I'm doing well in Linear Algebra, but I dunno how many hard problems we can find in this field. I don't think I can do this alone - maybe someone else take over for Calculus and Algebra (and I can contribute whenever I find an appropriate problem) and I'll manage NT, Combinatorics and maybe Geometry? Argh, the more I'm trying to organize this, the harder it seems. I'll just post some more cool problems tomorrow and see where the flow takes us, what kind of problems other anons post etc. And then we'll see.

>>8573437
Please, I just used the fact that [math] a ( \ln (n+1) - \ln n) + b ( \ln (n+1) + \ln (n+2) - 2 \ln n) \to 0 [/math] and this allowed me to go from the original series to the one I wrote. I also added a finite number of terms (3) in the beginning, which do not influence the convergence of the series.

>>8573449
Nope, in order to deduce that the original series converges, you don't just need [math]a(\ln(n+1) - \ln n)+ b(\ln(n+2) - \ln n) \to 0[/math], you need to prove that the series [math]\sum(a(\ln(n+1) - \ln n)+ b(\ln(n+2) - \ln n) )[/math] converges
(I mean [math]\sum \frac{1}{n^2}[/math] converges, but [math]\sum \frac{1}{n}+\frac{1}{n^2}[/math] diverges, although I added a sequence that goes to 0)

>>8573471
That's not necessary. I broke down every term in the original series into 3 terms (based on the number inder the logarithm) and regrouped them. That's where 1+a+b comes from. That's why I said I added a few terms in the beginning - those are a*ln 1, b*ln 1 (both 0) and b*ln 2.

File: great thread.jpg (177KB, 1600x1066px) Image search: [Google]

177KB, 1600x1066px

Bumping a dying thread and using this to dump a link. PS I'll do a whole bunch of C++ this year, I promise

https://youtu.be/7EeuMyRECPU