DAILY MATHS CHALLENGE THREAD

Daily maths challenge thread #1 (previously known as inter-major maths olympiad)
I admit the previous thread's problem wasn't worded perfectly, so this time I just cropped the problem text from the official source (IMO shortlist). This time we're having 2 problems, the first is a bit on the easy side and the second is harder. Feel free to discuss those problems and other similar ones. Let's stick to the maths stuff this time, okay?
Pic related is problem number 1.

Other urls found in this thread:

youtu.be/7EeuMyRECPU
twitter.com/AnonBabble

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"

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.

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.
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)

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

>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.

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 Veeky Forums. 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

Which one, user? I will try to clarify any questions you have.

Forget it, I'm a brainlet

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

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.

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?

Didn't read the hint, btw.

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?
what do you notice in step 5 and onwards? the pattern has a certain property you can control and use.

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.

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

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.
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").

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.

How can you prove that this pattern holds though?

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.

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.
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.

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

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).

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.

>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.

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 :/

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.

But that's not divergent.

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?

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

its just a negation of the statement

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]

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.
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 user 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?

Thanks user.

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.

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?

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

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?

I think the answer to b) is , 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 .
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 :)

>von neumanlett
I see what you did there

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?

I don't see it.

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)

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.

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

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

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

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

>I'm saying that I have no interest in geometry problems blah blah
user 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.

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

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.
T-thanks user 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.

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.

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

That's right, proof ?

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.

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.

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.

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

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

>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

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)

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.
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.

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.

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)

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.

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

youtu.be/7EeuMyRECPU