JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Nice article | Reply
The article is very nice, i hope another, a more advanced one comes through soon. Good effort.
Re: Nice article (response to post by vinay.emani) | Reply
I think it's very nice too.

My 2 cents...

Once I met problem “Derangements” on a math contest. The problem was to prove that f(n) always divisible by (n-1). Here f(n) - number of derangements, n>1. I solved it in slightly different manner.

Proof:

Statement is obvious when n = 2, so let n > 2

Consider two different possibilities:

1. Derangements like

1 2 ... i ... n
....... n ... i

not hard to see that there are exactly (n-1) * f(n-2) of them

2. All other derangements, so

1 2 ... i ... n
....... j ... i j != n

Let's forget about last elements in both rows.
If we look carefully, then we'll see that we can
painlessly rename "i" in upper row to "n" since j!= n.
And when we do that it becomes obviously that there are
exactly (n-1) * f(n-1) such derangements.

So, f(n) = (n-1) * ( f(n-1) + f(n-2) )
and is obviously divisible by (n-1).
Re: Nice article (response to post by it4.kp) | Reply
About derangements, the author remarks "This problem may not look very practical for use in TopCoder problems, but the thinking behind it is rather important, and these ideas can be widely applied."

Presumably such a derivation would have been practical for this TopCoder problem...
Re: Nice article (response to post by antimatter) | Reply
You right :)
And TC is not alone. You can see disguised version of this problem here:

http://acm.timus.ru/problem.aspx?space=1&num=1366
Re: Nice article (response to post by vinay.emani) | Reply
The article is very nice, i hope another, a more advanced one comes through soon.

I'll think of it :)
Re: Nice article (response to post by it4.kp) | Reply
One more: Valliadolid 10497 (Sweet Child Makes Trouble)
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1438

Solution and explanation is here: (in Russian)
http://mi.unicyb.kiev.ua/downloads/acm/Docs%20Valliadolid/Volume%20CIV/10497.htm
RSS