Wednesday, December 26, 2007

Russian CAPTCHA

Here's an innovative CAPTCHA I came across when trying to register for a forum at http://lib.mipt.ru/?spage=reg_user

You have to enter resistance between A and B in the diagram below. Can you do it?

5 comments:

mahatma-k said...

3 Kirhoff laws is all you need.
Странно, в мое школьное время (начало 80-х) такие задачки
были хлебом в 9-м и 10-м классе мат-школ. Чего такого заслуживающего в ней??

Yaroslav said...

Чего заслуживающего в этой задаче будет ясно из следующего поста :)

Stephen said...

Interesting. Seems like they are filtering more than just spambots.

Yaroslav said...

True, the CAPTCHA is probably there to filter out those pesky mathematicians, botanists and other non-physicists.

You can derive it directly from 2 Kirchhoff's laws (voltage around every loop is 0, net current at every node is 0), but it gets a bit messy. section 2.1 of Bollobas' "Modern Graph Theory" works out a simple example in detail using this method.

Most practical method is probably to use a CAS and a formula for 2-point resistance of general graphs (formula 2 of http://www.springerlink.com/content/ehddhc1cl2078cfa/), also see http://www.citeulike.org/user/yaroslavvb/article/1611063 for derivation

Without CAS, you could use parallel (conductances add), series (resistances add) and star-triangle laws (see Bollobas 2.1) to simplify the network into a single resistor

There are some interesting connections between theory of resistor networks and partition functions of statistical models. Alan Sokal (same one as the Alan Sokal hoax)
shows that partition function of Potts model has equivalents of parallel/resistance laws of electrical networks
http://arxiv.org/abs/math/0503607

Also, there's a 1-1 correspondence between electrical networks and reversible Markov chains (ie, http://www.citeulike.org/user/yaroslavvb/article/2081200), so you could potentially use theory of Markov Chains to solve this problem as well

L. Venkata Subramaniam said...

Do you think one day the author of this forum will not be able to solve the circuit theory problem and hence be unable to enter?

I am speculating that he will forget to solve it soon after his 80th birthday. I hear thats when the resistance of the neuron sheaths breaks down and the charge carrying capacity comes down drastically.