@SiddharthJoshi: Hello!

Hey @user21820

Feel free to continue here if you like.

If I remove the last step A->B, does it make any difference to the proof

For reference, we're discussing this post:

yes

@SiddharthJoshi It does because you want to modify the subpath to 'reduce' the 'backwards badness'.

If it is A→B→C→D→C→B→A, what are you going to change it to, and can you show that it is doable?

That is why I have to chase all the way to the last two backward moves in the first backward chain of length at least 2.

I see

So that after that it must go forward, having C→B→A→B, so that I can then move that "B→A→B" forward.

There is still some work that has to be done to show that performing such improvement steps eventually terminates with the desired "no backwards twice".

I didn't include that in my comments.

Yeah I felt a rigorous proof would be too involved for that

Actually there is a simple trick to do that last bit. I'll sketch it here for you.

Consider the number of inversions (i.e. pairs of points (p,q) such that p is before q.

It is finite, and every time we make an improvement of the described sort, we decrease the number of inversions.

Clearly, it cannot go below zero, so eventually we can't make any more improvements.

This depends on the fact that in the subpath the "..." stays at C or later, so that the inversions involving the swap of the "..." and the "B→A→B" will actually decrease the number of inversions.

If you don't get this, feel free to ask. Counting inversions is a very widely used technique in lots of fields in mathematics. =)

What are pairs of points (p, q) such that p is before q

are those points in the sequence traveled by the Camel?

Pardon me if I ask too many questions .. I will try my best to understand on my own unless very unclear

Yes, pairs of points in the path. For example in the path A→B→C→D→C→B→A, we have 7 points and C(7,2) pairs that we need to check. Let me label them so that I can describe the inversions.

1A→2B→3C→4D→5C→6B→7A

Where A < B < C < D, where "<" means "before".

cool

Sorry! I meant to say "such that p is after q".

what are the inversions here?

So the pair (3C,6B) is an inversion because C > B.

got it

(2B,7A) is also another inversion.

Now consider the improvement from:

A→B→C→...→C→B→A→B

to:

A→B→A→B→C→...→C→B

You can see that the number of inversions is not changed except possibly for those pairs involved in the swapped parts.

But the "A" is moving forward, so all those involved inversions that involve A are disappearing.

Again one more doubt - "..." in the sequence above would not involve A or any point to the left of it right?

@SiddharthJoshi Right, the choice of "first backward chain of length at least 2" ensures that "..." has nothing before C.

right

So both the B and the A are hopping over that middle part, and the inversions between those two parts disappear.

There may still be inversions inside each part, and elsewhere.

But all that matters is that the pairs affected by the swap have now less inversions.

yes makes sense

so I should try to prove that reducing inversions makes the sequence traversable as well as doesn't decrease the final amounts?

No those are two separate issues. You need to prove that each improvement reduces the inversions as well as preserves the validity of the path, separately. These together ensures that if you keep making improvements you must eventually end up with a valid path that has no "backward chain of length at least 2".

If you don't prove that the improvements reduce inversions, it is not obvious that you will end up with no "backward chain of length at least 2". Namely, what if you keep finding backward chains of length at least 2?

If you are familiar with this inversions trick, then the hard part is the other issue, that's why I focused on it. But I kind of forgot that the inversions trick is not really easy to find if you haven't learnt it somewhere before.

Ok so this was just to prove that you can finally have a no earlier point sequence if we go on making such changes?

Right!

Cool - this is really not a trivial problem as the other answers in the post made it seem - and I am glad someone realized it - let me make use of some of the insights discussed here to come up with a formal proof ( I'm sure you can - but that would require a lot of effort for you to write down )

@SiddharthJoshi Indeed it would make an excellent exercise for you. =)

thanks

I am also really glad that people are discussing this cute problem and its solution, partly because it's cute and partly because it's one of the very first posts I ever wrote on Math SE!

@SiddharthJoshi: By the way, have you done some basic group theory before? Counting inversions is the simplest rigorous way I know to define the parity of a permutation and to prove that each swap flips the parity.

Hey yes I know group theory and inversions ( such concepts are used in competitive programming as well - finding minimum number of swaps of adjacent elements to sort an array, etc. and many more ). But It didn't even occur to me that I should use it here to make the proof complete.

I am also curious what math education you have.. since the only exposure I have to proofs, puzzles and such problems is through competitive programming or some puzzling website, though I really want to getter better at it.

As for the question, I believe I can extend my reasoning to calculate amount on B to prove that the amounts are greater than or equal to the amounts before swapping.

@user21820 $f$ is positive continuous periodic function with period 1. Are the average value of $f(x+a)$ and $f(x)$, $a\in \mathbb R$ same?

I think we have to prove $$\int_{0}^{1} f(x+a) dx = \int_{0}^{1} f(x) dx $$

@SiddharthJoshi I am familiar with most of undergraduate mathematics plus a fair bit of olympiad stuff plus more advanced stuff in logic and theoretical computer science. If you're interested in learning the logic that underlies mathematics, you need to learn to use a deductive system for FOL (first-order logic).

If we do the substitution $u=x+a$ we would get $$\int_{0}^{1} f(u) du = \int_{0}^{1} f(x) dx $$ I understand that $u$ and $x$ Are just dummy variable, but I still don’t feel like accepting it. Can you help me in convincing myself ?

@SiddharthJoshi I'm not sure what you mean by "your reasoning". As I said earlier, the improvement step you described does not work. And if you mean that you want to use your reasoning applied to the improvement step I described, I have doubts that it would work, because I don't think there is any easier way than what I sketched (tracing the bananas used in the "B→A→B" part that is moved forward).

@Knight You cannot say "average" without saying over what interval. Your integrals suggest that you want the average over [0,1], in which case they are the same.

But I don't really understand what you mean by "dummy variable". There is actually no reason to use substitution. Just split the integral into two parts.

@user21820 How to split?

@Knight Use the intuition that the integral when the graph is shifted by a is the same because it can be divided into two parts which can be translated to match the original integral. It's easier if you draw the diagram and look at what you want to prove in terms of area under the graph.

(Anyway your substitution is wrong because you of course have to change the limits if you substitute the variable of integration.)

Got it thanks

If you like, you can write it out and I'll check it.

@user21820 I need your help regarding the exponential form of Fourier series

For a periodic function of period $T$, we define $\omega =\frac{2\pi}{T}$ and we have $$f(t)= \sum_{n=-\infty}^{\infty} c_n e^{i\omega n t}$$

Then, is the average value of $f$ is $c_0$ And is it same thing as $a_0$ in our trigonometric Fourier series?

Let me repeat again:

> You cannot say "average" without saying over what interval.

Being precise is very important.

I'll be away for quite a while. I'll respond when I'm back.

Average over the interval $[0,T]$

Okay I shall wait

Yeah I perfectly understand that my reasoning for the improvement step is incorrect. I was actually talking about proving that all bananas have at least as much bananas at the end of the sequence resulting from the improvement step as they have earlier. Nevermind, I get the idea from your sketch and will write a detailed proof when I have time ( instead of bothering you here :) )

@Knight Then there is something wrong with your expression. e^(iωπt) does not have the period you seem to want.

@SiddharthJoshi Oh. Hmm it depends on what you had in mind for the moves. In the original subpath, you might bring some bananas with you in the "..." that eventually get consumed during the "B→A→B" after that. Some of those 'moves' have to all be changed, because you need to leave the appropriate bananas behind. So in fact I was merely describing how to modify those moves (trace those bananas and leave them behind instead of bringing them along in "...") in a manner that makes it obviously valid.

We can't just swap the sequence of moves without altering the quantities brought, and this seems to be the easiest way to describe that. In case it is not clear, leaving bananas behind does not increase the number of bananas carried in the "...", so we won't violate the capacity constraint.

@Knight: Sorry I misread your "n" as "π". Lol!

@Knight So indeed e^(iωnt) has period T as long as n≠0, and if you do the integration over [0,T] you see that it is zero. So all that is left is the constant term which comes from e^(iω0t) = 1.

@user21820 What's the average value of such a function? Is it $c_0$?

Indeed the average of your f over [0,T] is just c[0], based on the reasoning above.

Okay Thanks

That is under the assumption that your f is well-defined.

Yes it is continuous

If you have not proven that the infinite sum converges, then you don't have f.

It is given that f is bounded

@Knight If the original function is periodic and continuous, it will indeed be bounded, and I do believe that the fourier series is well-defined as well. (It's a long time since I touched that stuff so I'm not 100% sure.)

( I don't know why but I know things but I need to confirm it with someone experienced, I just doubt myself)

That's fine. I do that too.

:)

Thanks

See you later, have a wonderful day

Sometimes, talking to interested people can help even if they are not 'more expert' than you. It's called rubber duck debugging. =)

@Knight See you later!