/sci/ - Science & Math

This question seems ill-posed. Do the integers have to be positive or is does their sum have to be positive?

>>4399506
Obviously, the sum must be positive.

>>4399506
The sum must be, the individual integers don't.

>>4399675
>>4399595
>>4399506
Well, actually the sum doesn't have to be positive. Just take that all labels have negative numbers. Then the statement holds true

>>4399692
No, then the sum wouldn't be n-1.

That property is kinda cool.

>>4399752

-20 <= 8

Trying by induction.

Base case is trivial.

Consider you have <span class="math">n[/spoiler] beads and at least one of them is tagged <span class="math">1[/spoiler]. Then the <span class="math">n-1[/spoiler] other beads can form a sequence with the property we want if we remove the bead <span class="math">1[/spoiler]. Now we take this sequence, we add the bead <span class="math">1[/spoiler] where it should have been, and the property is still there. Note that if the bead <span class="math">1[/spoiler] is supposed to be where the necklace of length <span class="math">n-1[/spoiler] was cut, you have to add it at the end of the sequence of length <span class="math">n-1[/spoiler], since the first bead of the sequence must be <span class="math">\leq 0[/spoiler].

So if the property holds for a given necklace, and we add a bead that weights <span class="math">1[/spoiler] anywhere on that necklace, the property is kept. That's not much but that's a start.

>>4399758
Read the question again. The sum of all the beads is n-1.

>>4399758
The partial sums can be negative. The overall sum must be n-1. Read the problem statement again maybe.

Well, here is what I got:

The statement says:
<span class="math"> \exists such \ cut : \ \forall k=1,2, ... n [/spoiler]
the property is true

Try indirect proof (absurdum):
<span class="math"> \forall \ cut \ \exists k=1,2...n [/spoiler]

such that the weak inequality in the sum changes to strong inequality to the other side for some k.

If it is for every cut so let's choose one random.
Let k=p

Such "p" might be not the only one. So let's take the greatest possible "p" for which our hypothesis is true.
The sum from 1,...,p is greater than p-1, but the sum from 1,...,n is not greater than n-1. From this we get that the sum from p+1,...,n must be less than n-p. So the sum form p+1,...,n satisfies the original inequality and if it now is followed by 1,...,p the hypothesis is not satisfied. End.

Maybe this is some kind of idea. The problem would be with proof that the hypothesis isn't true for some earlier p.

herp derp

It's somewhat funny.
On every other Putnam problem except this and previous one, people had complete answers and proofs within an hour or less and discussed how easy it was or how dumb other people are. And here come these two problems and magically all those smart people have disappeared.

Go easy on me /sci/ my first attempt at a full putnam proof, It lacks rigor, but I'm hoping it's the right idea. shortened and poorly formatted as its from a phone. Let s be that sum in the op.

For every cut length k, there are n possible cuts, since you can start from any <span class="math">x_n[/spoiler]. Now we suppose for a contradiction S greater strictly than k-1 which is equivalent to S greater or equal k since we are working with integers. Each xi appears in exactly k permutations (this may need a proof) so k(x_1....x_k)greater or equal nk dividing through by k we have S greater or equal n. which is a contradiction as letting n=k yields S greater or equal n which is false as S=n-1.

I will latex it later, if I have time and it isn't debunked!

>>4400313
looks right

>>4400296
Problems in Putnam tests are organized in two times six problems of increasing difficulty. The last problem I solved was the one that discussed the convergence of the integral of the difference between square roots of differences of square roots. That particular problem was one of the first of a series and was really easy. It was solved twice in the first two hours after it was posted.

Now, we're 2 problems further high in the difficulty scale of Putnam's problems. It makes sense that people don't find the solution as fast (or at all).

If you check the archives of the Putnam threads and compare them to the archive of the Putnam competition, you will see a decent correlation between how early the problem is in the competition and how many people solved it on 4chan. Although of course, sometimes a hard problem has its solution posted here because someone thought it was fun to find the solution online.

Consider that the necklace's beads are, in order but starting at an arbitrary bead, <span class="math">(b_1,\dots,b_n)[/spoiler]. Now we consider the set <span class="math">\mathcal{X} =\{(x_1,\dots,x_n)~|~( x_1,\dots,x_n) [/spoiler]is a cyclic permutation of <span class="math">(b_1,\dots,b_n)\}[/spoiler].

We consider n>1 (n=1 is trivial). Consider that the statement of the problem is false. Then for each <span class="math">(x_1,\dots,x_n)\in \mathcal{X}[/spoiler], there is k such that <span class="math">\sum_{i=1}^kx_i\geq k[/spoiler]. For a given sequence <span class="math">X=(x_1,\dots,x_n)\in \mathcal{X}[/spoiler], let us denote by <span class="math">k(X)[/spoiler] the smallest such <span class="math">k[/spoiler]. Let us now consider <span class="math">X_0[/spoiler] a sequence which maximizes <span class="math">k(X)[/spoiler] and write <span class="math">k(X_0)=k_0[/spoiler]: we have <span class="math">\forall X\in\mathcal{X},\ k(X)\leq k_0[/spoiler]. Clearly, <span class="math">k_0>1[/spoiler], otherwise every <span class="math">b_i[/spoiler] has to be non-positive and their sum cannot be <span class="math">n-1[/spoiler].

We can write <span class="math">X_0=(b_{a+1},\dots,b_{a+n})[/spoiler] for some integer <span class="math">a[/spoiler], with modulo n sum. And we have <span class="math">\sum_{i=1}^m b_{a+i}\leq m-1[/spoiler] for all <span class="math">b\leq k_0[/spoiler]. Now if <span class="math">b_{a+n}\leq 1[/spoiler], then for all <span class="math">m<k_0[/spoiler], we have
<span class="math">b_{a+n}+ \sum_{i=0}^m b_{a+i}\leq 1+(m-1)[/spoiler]
<span class="math">\sum_{i=0}^{m+1} b_{(a+1)+i}\leq (m+1)-1[/spoiler]
and <span class="math">k(b_{(a+1)+1},\dots,b_{(a+1)+n})>k_0[/spoiler], which is a contradiction. Therefore, <span class="math">b_{a+n}> 1[/spoiler].
The same reasoning extends to <span class="math">b_{a+n}+b_{a+(n-1)} >2[/spoiler], and eventually to <span class="math">\sum_{i=k_0}^n b_{a+i}> n+1-k_0[/spoiler].
Therefore,
<span class="math">\sum_{i=1}^n b_i= \sum_{i=1}^n b_{a+i}= \left(\sum_{i=1}^{k_0-1} b_{a+i}\right) +\left(\sum_{i=k_0}^n b_{a+i}\right) >(k_0-2)+(n+1-k_0)=n-1[/spoiler].

This is a contradiction, and we're done.

>>4400529
Shut up, TN5. Nobody likes you or your posts.
Stop shitting put putnam threads.

>>4400555
Damn, I knew I shouldn't have posted as anon in the last few threads. I missed my fan club. You don't know how much your support means to me, anon!

>>4400568
Shut up, shitposter.

>>4400576
>sageing a sticky and shitposting
>calling people who contribute shitposters
You're supposed to pick one.

>>4400555

i can almost touch your envy

>>4400529
The two sums that start at 0 should start at 1.

>>4400529
To be honest, I didn't quite follow that proof.
I have a more constructive proof in mind.

Assume that a cut [x_0, ..., x_n] with the desired properties exists, then, if we take decrease bead x_i by m and increase x_(i+1) by m, we obtain a different chain that also has a cut with the desired properties. (All sums of the new chain are equal to the original, except for the sum up to x_i, which is smaller, hence the desired property must hold.) We refer to that operation as 'redistributing' the chain. The inverse of redistributing, we call 'rebalancing'.
>ctd

>>4401086

A chain consisting only of beads with values 0 and 1 has only one solution, namely one starting with 0, and only 1's following. Refer to this chain as the base chain. Now, it suffices to prove that every chain can be obtained by redistributing the base chain, which is equivalent to proving that the given chain can be rebalanced to the base chain.

Rebalancing allows us to move a number from a highly ranked bead to a lower ranked bead. However, we don't know the location of the cut yet. We, therefore, move numbers counter-clockwise one step, and run the risk of decreasing x_0 and increasing x_n. It is trivial that this operation can be performed in such a way that we end up with the base chain. However, we need to proof that the disallowed step from x_0 to x_n did not occur (but we haven't fixed the location of the cut yet). We can inspect how much we moved between each neighbouring pair of beads. If the minimum value is 0, then we're done, there is the location of the cut. If the minimum value is l, then note that if we decrease each movement with l, we also end up with the base chain, and we have a movement of 0 somewhere.

Each chain can be transformed into the base chain by rebalancing, which implies that chain can be formed by redistributing the base chain. Since redistributing doesn't break the desired property, the desired property must hold for all chains.

>>4401086
But you aren't allowed to switch two beads. The order must be preserved, only the place at which you cut can change.

My proof says that if you consider, among the n possible cuts, the cut that maximizes the number of beads that you can add together until you finally break the <span class="math">\sum_{i=1}^k x_i\leq k-1[/spoiler] property, then you could have cut one bead further left instead unless that new first bead is greater than 1. If you had cut one bead further left, you would have had a cut that has an even higher number of beads that you can add together until you break the property, which is a contradiction. So that bead is greater than 1. Now if you consider what happens when you cut two beads further left, you'll see that the condition becomes that their sum is greater than 2. Etc. And if you add all of these together, the sum of all the beads will be higher than n+1.

>>4401090
Oh, forgot one detail. The base chain must start with a 0, so the chain must also start with a 0 after rebalancing.
It's possible that the method of rebalancing as described happens to place the cut at the right location (that is, there are no movements to the left, for a bead labelled 0). Assume, therefore, that the bead labelled 0 had movements to the left. We can decrease its movement by 1. Then the bead will be labelled 1, and its left neighbour will be labelled 0. If we continue doing this, we must hit a bead that had no movement to the left, since there exists such a bead by construction.

>>4401113
I'm not switching beads.
If we have to beads, x_i and x_(i+1), with values 10 and -4, and they exist in a cut for which the property holds, then certainly the property holds if x_i and x_(i+1) had the values 5 and 1. This invariance is the basis of the proof.

>>4401136
More precisely, I prove that every chain can be constructed from the base chain (with suitable rotation), and that operation that doesn't break the property. I imagine that the proof is a bit unreadable, because I'm tired, and I don't really care, since I'm convinced of it's correctness. I do understand your proof now. Works too.

>>4401136
Okay, my bad, that's why I didn't get what you mean when you talked about the forbidden change between the first and last of the chain.

>>4401189
>That feel when TN5's ass will never be on your dick

>>4401234

But you're black! Use dat swag brah.

>You will never solve a putnam problem.

This problem is solved in exactly the same way as the "Add a person to a full Hilbert Hotel" problem, only backwards.

>>4399477
all of these goddamn things involve serieses dont they

So this answer was deleted a while ago by whoever posted it (although not in tex):
Assume that, for some k, all such sums are greater than k-1. Let <span class="math">y_j = \sum_{i=j}^{j+k-1} x_i \ge k[/spoiler] (where coefficients are taken mod n). Then <span class="math">\sum_{j=1}^n y_j \ge kn[/spoiler]. But this sum counts each bead k times, so we must have <span class="math">\sum_{j=1}^n y_j = k(\sum_{i = 1}^n x_i) = k(n-1)[/spoiler], a contradiction.

http://www.wolframalpha.com/input/?i=abs[%28x%29%2F%282%28x%29^0.5%2B1%29]%3C1%2F3

how do i ask wolfram to show me the steps solving this?

>>4402671
But you assume that there is a <span class="math">k[/spoiler] for which for each possible cut, the sum of the first <span class="math">k[/spoiler] beads is above <span class="math">k-1[/spoiler]. There is no guarantee that it has to be the same <span class="math">k[/spoiler] for each cut that would make the property fail.

TN5, please stop posting.

>>4403449
seconded

TN5 has to shut up.

There sure is samesagefagging in here.

>>4403604
TN5 always samefags to maximize the damage he does on putnam threads.