Google入社試験で，「無限格子の電気抵抗」を求める問題の解答と解説

「数学が得意」とか「物理が得意」「回路ならまかせろ！」と自負する人には，

次のシンプルな問題を解かせてみよう。

問題：（Google入社試験より）

二次元平面上に無限に続く、１オームの抵抗で作られた正方形の格子において、ナイトの動き(桂馬飛び)の位置にある２つのノード間の抵抗は？

これは，Googleの入社試験の中でも，特に難解な問題。

What is going on ? - Google Labs Aptitude Test
http://www.whatisgoingon.net/glat.html

On an infinite, two-dimentional, rectangular lattice of 1-ohm resistors, what is the resistance between two nodes that are a knight's move away ?

二次元平面上に無限に続く，１オームの抵抗で作られた正方形の格子において，ナイトの... : 入社試験・面接試験の奇問難問をまとめてみたぜ
http://matome.naver.jp/odai/212960316...

二次元平面上に無限に続く，１オームの抵抗で作られた正方形の格子において，ナイトの動き(桂馬飛び)の位置にある２つのノード間の抵抗は?

この問題を解くために必要な知識は...

「線形回路」の高度な扱い方（※フツーの電気回路に加えて，「重ね合わせの理」などの理論を知っている必要がある）

マクスウェル方程式の意味をよく理解した程度の電磁気学

n 次の漸化式の，特性多項式を使った解き方

フーリエ級数を一般化した積分を，計算機に解かせるぐらいの高度な扱い方

など。

下記では，この問題の答えを導出し，簡潔に解説してみる。

以下，略解

整数の格子点を (x, y) の２変数で表す。

格子状の抵抗が無限平面上に続いているとして，

(0, 0) と (1, 2) の二座標の間の抵抗を求めればよい。

そのために，まず (0, 0) と (1, 2) の二座標の間の電位差を求める。

原点 (0, 0) に対して１Ａの電流を注入する事を考える。

注入された電流は，無限遠へ流れてゆき発散する。

この場合，キルヒホッフの法則により，原点以外のどの座標をとっても，

電流の湧き出しと吸い込みの和が 0 である。

この事を数式で表すと，ある座標における電流と電圧の関係は

$I_{xy}\\=(V_{xy}-V_{x+1,y})+(V_{xy}-V_{x,y+1})\\+(V_{xy}-V_{x-1,y})+(V_{xy}-V_{x,y-1})\\=4V_{xy}-V_{x+1,y}\\-V_{x-1,y}-V_{x,y+1}-V_{x,y-1}\\=0$

となる。

これはVについての漸化式であり，普通なら特性多項式を仮定して解くのだが，いろいろ特性多項式を試しても解けないので，その路線はあきらめる。

そこで，かわりの方法として，電圧V が下記の（フーリエ変換のような）形で書き表せる事を仮定して，上記の式を解く事にしてみる。

$V_{xy}=\int_{0}^{2\pi}d\beta{}F(\beta{})v_{xy}(\beta{}),\\v_{xy}=e^{i|x|\alpha{}+iy\beta{}}$

ただし，αはβの関数であるとする。

これを前の式に実際に代入してみると，

$4V_{xy}-V_{x+1,y}\\-V_{x-1,y}-V_{x,y+1}-V_{x,y-1}\\=\dots{}\\=2e^{ix\alpha{}+iy\beta{}}(2-\cos{}\alpha{}-\cos{}\beta{})=0$

という方程式になる。

これをαについて解くと

$\alpha{}=\\i\log{}(2-\cos{}\beta{}\cdot\\\sqrt{3-4\cos{}\beta{}+\cos{}^2\beta{}})$

となり，ここまでの仮定を満たすようなα，βの組み合わせが確かに存在する事が分かる。

したがって，先に述べたVの積分形式での表記は成立するものとして論議を進めてよい。

ここで，x = 0 における電流を求めると

$I_{0y}\\=4V_{0y}-V_{1y}-V_{-1,y}\\-V_{0,y+1}-V_{0,y-1}\\=\dots{}\\=\int_{0}^{2\pi}d\beta{}F(\beta{})e^{iy\beta{}}(4-2e^{i\alpha{}}\\-2\cos{}\beta{})\\=\dots{}\\=\int_{0}^{2\pi}d\beta{}(-2iF(\beta{})\sin{}\alpha{})e^{iy\beta{}}$

これはフーリエ級数展開の形をしているから，

その点を利用して，カッコ内をフーリエ級数の係数とみなす事により，次式のように書ける。

$-2iF(\beta{})\sin{}\alpha{}\\=\frac{1}{2\pi}\sum_{y=-\infty{}}^{\infty}I_{0y}e^{-iy\beta{}}$

ここで，電流は原点に１アンペアを注入する前提であったから，原点以外では

$I_{xy}=0$

である。この性質を利用して，関数 F(β)を求めると

$F(\beta{})=\frac{i}{4\pi\sin{}\alpha{}}$

となる。

よって，任意の座標 (x, y) について，積分変数βと，βについての既知の関数αを使って，電位を下記のように表わせる。

$V_{xy}=\frac{i}{4\pi}\int_{0}^{2\pi}\frac{d\beta{}}{\sin{}\alpha{}}e^{i|x|\alpha{}+iy\beta{}}$

これで電位が求められた。

次いで，この電位をもとに，２点間の抵抗を求める。

まず，単純な電位の差として

$V_{00}-V_{xy}$

を計算しただけでは，原点との間の抵抗を求めた事にはならない，という点に注意しよう。

冒頭で述べた通り，原点に注入した電流は，無限遠に発散しており，閉じた回路が形成されていないのだ。

だから，ここで仮想的に，点 (x, y) において，１Ａの電流吸い込みが発生する状況を考える事にする。

点 (x, y) の電流吸い込みは，無限遠から電流を吸引している事になる。

また，この電位のポテンシャルは，原点での電流注入が発生させる電位のポテンシャルの符号を逆にして，座標の分だけずらしたものになる。

このような２つの電流原を線形回路として重ね合わせると，重ね合わせの定理により，無限遠での電流の発散が相殺され，閉じた回路が生まれる。

このように，原点に１Ａを注入し，点（x, y）から１Ａが返ってくる回路において，この両端子の電位差を求めればよい。

重ね合わせの結果より，もともと計算してあった電位差を２倍すればよいから，原点からの抵抗は

$R_{xy}\\=2(V_{00}-V_{xy})\\=\frac{i}{2\pi}\int_{0}^{2\pi}\frac{d\beta{}}{\sin{}\alpha{}}e^{i|x|\alpha{}+iy\beta{}}$

のようになる。これが，抵抗の一般解となる。

そして，もともとの問題では，原点と座標（1，2）の間の抵抗を求める要求であった。

この数値を（x, y）に代入して積分を（Methematicaなどの計算機で）実行すると，答えは

$-\frac{1}{2}+\frac{4}{\pi}$

となる。

（模範解答の終わり）

回答のために参考にしたページ：

無限に広がる抵抗ネットワークの合成値 - 趣味の世界
http://bal4u.dip.jp/hobby/2013/08/pos...

この種の問題はドクター論文であったり、学術論文になっているので、大変奥深い数学問題になっている。円周率Πが答えに含まれるので、代数方程式では到底答えが出せない。

はてさてブックログ - [非公認] Googleの入社試験：あきらめました・・・。
http://hatesate.dip.jp/weblog/2008/08...

実はその分野の中でも「超難問」だそうで。物理学の論文が何本もでているそうで・・・。この解は、積分（いわゆるミミズです）やら、自然対数の底（ｅというやつですね）やら、三角関数（sin、cosとかいうやつです）やらを使った「公式」があって（知るか、そんなモン！）、それを使って（もちろんコンピュータで）解かないと、導き出せない

Infinite Grid of Resistors
http://www.mathpages.com/home/kmath66...

a well-known puzzle based on the premise of an “infinite” grid of resistors

Google入社試験の「無限格子の電気抵抗」の問題の解法
http://study-guide.hatenablog.jp/entry/20131031/p2

これは，並みの数学と電気回路の知識では解けない