I am sure all of you have encountered CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) tests before. CAPTCHA tests are generated by computers, but only humans should be able to solve them. Hence, one can tell human users from computers.
A few weeks ago, Yaroslav Bulatov wrote a post about a Russian CAPTCHA that he encountered at the Московский физико-технический институт library website:
January 25, 2008 at 13:10 |
It’s e-library of MIPT, Moscow Institute of Physics and Technology, university I graduated from :), so test is some crazy equivalent of on-campus access restriction.
January 25, 2008 at 13:28 |
Holy Kirchhoff!
That’s from MIPT for sure! :)
January 25, 2008 at 13:30 |
In Russian it’s “МФТИ”, “Московский физико-технический институт” [Moskovsky fiziko-tekhnicheskiy institut], literally Moscow physical-technical institute. MIPT is most commonly referred to as simply “ФизТех” (“PhysTech”).
January 26, 2008 at 16:38 |
Fewf, it was really tough. I tried solving it in the general case, here is an illustration so you can get the designations:
http://www.box.net/shared/5to9xaow08
The answer is (numerator and denominator split by “—-”):
(n2+n4)*(n1*y+n5*x)+(n1+n2)*n4*x
——————————————–
(n1+n2)*y
, where:
x = n3*n2-n1*n4
y = (n1+n2)*(n3+n4)+(n1+n2+n3+n4)*n5
I’ll post the complete solution later as a trackback from my blog
PS Note that you don’t have to reduce the resulting fraction in this captcha, e.g. if 5/20 is the answer, you can enter 5/20, 1/4, 10/40 etc.
PPS A question of ethics, do you think I have the right to disclose the answer?
January 27, 2008 at 03:47 |
I also ended up sidetracking for more than a few hours because of this problem, mostly because of stumbling onto some fascinating connections of resistor networks to other field of math, a few papers at http://www.citeulike.org/user/yaroslavvb/tag/resistance
The lazy approach to solve this is to use a general formula for 2-point resistance between nodes in an arbitrary graph, see second formula on page 7 of http://arxiv.org/abs/math-ph/0402038 and recognize that the limiting definition of g is equivalent to Penrose-Moore pseudo-inverse
Function resmat (Mathematica) below generates the matrix of effective resistances from a matrix of edge-wise resistances
lapl[m_] := DiagonalMatrix[Array[1 &, Length[m]].m] – m;
resmat[m_] := Module[{n = Length[m]},
g = PseudoInverse[lapl[m /. {x_?Positive -> 1/x}]];
Table[g[[i, i]] + g[[j, j]] – g[[i, j]] – g[[j, i]], {i, 1, n}, {j,
1, n}]
];
To get an answer for the problem above you do
resmat[{{0, 1, 3, 0}, {1, 0, 6, 2}, {3, 6, 0, 3}, {0, 2, 3, 0}}][[1, 4]]
to get 147/74
I’m curious, could this approach be adapted to work in Matlab? (ie, how would you get an exact fraction?)
January 29, 2008 at 01:03 |
Here’s an outline of 8 ways you can solve this problem, feel free to suggest any I missed
August 16, 2011 at 22:57 |
http://reblot.am/capcha/ResistanceCalculator.html
Use this link to calculate Resistance :)