[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 9 KB, 547x123, day.gif [View same] [iqdb] [saucenao] [google]
4408162 No.4408162[STICKY]  [Reply] [Original]

Putnam/Olympiad problem of the day from
http://math.harvard.edu/putnam/

>> No.4408168

first

>> No.4408292

>>4408168
fag

>> No.4408337

Let's consider <span class="math">a'=a-2n[/spoiler], <span class="math">b'=b-2n[/spoiler] and <span class="math">c'=c-2n[/spoiler]. They can be obtained by asking the <span class="math">n[/spoiler] people to write <span class="math">-1[/spoiler], <span class="math">0[/spoiler] and <span class="math">1[/spoiler] instead of <span class="math">1[/spoiler], <span class="math">2[/spoiler] and <span class="math">3[/spoiler], and following the same rules.

Let's check what can happen to these lines when a new column is written.
The only way to end up with <span class="math">a'=b'=c'[/spoiler] is if we had <span class="math">a'+2=b'+1=c'[/spoiler] before writing the new column, and we luckily got <span class="math">+1[/spoiler] on <span class="math">a'[/spoiler], <span class="math">0[/spoiler] on <span class="math">b'[/spoiler] and <span class="math">-1[/spoiler] on <span class="math">c'[/spoiler] (which happens with probability 1/6).
However, ending up with <span class="math">a'+2=b'+1=c'[/spoiler] happens with probability <span class="math">1[/spoiler] if we had <span class="math">a'=b'=c'[/spoiler], and we can also get there from other states of the system.

The probability to stop with state <span class="math">a'=b'=c'[/spoiler] is therefore asymptotically at least <span class="math">6[/spoiler] times lesser than the probability to stop with state <span class="math">a'+2=b'+1=c'[/spoiler], so we can find <span class="math">n[/spoiler] as large as we want such that the ratio is at least <span class="math">4[/spoiler].

Does this make sense?

>> No.4408591

Looked up the answer. Pretty sure no one will get this.

>> No.4408623

>>4408591
Is >>4408337 wrong?

>> No.4409493

...Numbers.

I don't even know how I got here I was on TVTropes then I clicked this link for porn and now I'm here and I'm confused.
I didn't even know /sci/ had math I've never been to this board before why do I have a boner

>> No.4409640

>>4409493
Since when did tv tropes allow you to post porn

>> No.4410374

>>4408337
Please stop.

>> No.4410517

>>4408337
The 6 times less isn't a direct conclusion.
Where do you conclude that from?

>> No.4410824

>>4410517
Yes indeed, and it is wrong. My reasoning was intuitively "We have a random process that adds columns. This process is memoryless and has all the "good" properties that we want on a Markov chain, in particular irreductibility and ergodicity, so the distribution probabilities that we are on a given state converge". If that was true, then my claim would have been correct, because the limit distribution would satisfy that <span class="math">Pr(a'+2=b'+1=c') = 6\cdot Pr(a'=b'=c')[/spoiler]. However, this limit distribution is only guaranteed to exist when the number of states is finite, and we have a countably many states here (for instance, a' can be as small as we want).

I tried thinking of how the number of states could be made finite, maybe by setting a maximum distance from the equilibrium after which we don't move anymore, but I can't get a proof out of it.
Also, by trying to manipulate the probabilities directly and assuming that the statement of the problem is false, I end up with a strong constraint on the probability <span class="math">y_n[/spoiler] that we are, after <span class="math">n[/spoiler] columns, on the state <span class="math">a'+2=b'+1=c'[/spoiler], that is, <span class="math">y_{n+1}\in \{7y_n/12,8y_n/12\}[/spoiler]. Too bad, that was almost enough for a contradiction. The fact that I obtain this by plugging "4" makes me think that 4 is a clever choice and that 5 or 6 wouldn't have worked. But I don't know why.

TL;DR: my proof above doesn't work, and I don't know how to make it work, sorry.

>> No.4410848

>>4410824
Please stop. You never solve these problems. Instead, you spend paragraphs processing your internal dialog. You are not appreciated.

>> No.4410886

>>4410848
If you're looking only for a correct answer, there are places you can go for that. Thought processes, suggestions for how to approach a problem, and incomplete attempts are appropriate here.

>> No.4410889

>>4410886
I agree. All those depictions are non-issues.

Altering the problem by introducing a set of assumptions that makes the problem ridiculously simple along with endless prattling why the same technique on such a glorified alteration of a problem is unsuccessful against the original, is an issue.

>> No.4410895

>>4410886
Just ignore him. He doesn't like me and should ignore my posts, he chooses not to, that forces the rest of us to be the mature ones and ignore his. Not a big deal. At least every single of my posts is acknowledged, which is kinda cool.

>> No.4411024

>>4410895
Stop derailing. The thread is not about you, but about the putnam problem.

>> No.4411041

>>4411024
Who's derailing the thread? He posted 2 of the 3 answers actually related to the problem. You answered and caused these 7 stickysage off-topic replies, 4 of which are yours I think. And I'm assuming that you will reply to this, making it 5 useless posts, without doubting yourself for a second...

I'm starting to wonder whether you're not just trying to make these Putnam threads worse on purpose.

>> No.4411051

>>4411041
TN5, please stop posting.

>> No.4411993

>>4411051
You are one sad little man.

On an unrelated note. Why is this putnam of the day unsolved?
Who still wants to think about this one? (Today's is trivial, but tedious)

>> No.4412007

>>4411993
Why is it still unsolved?

Because TN5 derailed the thread.

Seriously, this guy should just drop his tripcode. No one needs a trip in a math thread. He wants to show off with his stupid latex spam and this annoys other posters.

>> No.4412497

>>4411993
This one is harder than most. Putnam competitions are made of two times 6 problems of increasing difficulties, this one is the sixth of the first part of the 1995 competition. /sci/'s success rate on the last problems is sensibly lower than on the first ones.