◆東京都 boltさんからの解答。
どんな自然数nでも、うまく自然数（非負の整数）
m,x[0],x[1],...,x[m]を取ってくれば
n=x[0]*10m+x[1]*10m-1+...+x[m]*1（※）
と書くことができるので、
あるnに対し、具体的にどのように
m,x[0],x[1],...,x[m]を取ればよいのかを考える。
適当な自然数nをとり、最も簡単な上のような表現をまず考える。
すなわち、10a≦n＜10a+1となる非負の整数aと、
0≦m≦aであるようなmに対し、
0≦y[m]≦9であるような非負の整数y[0],y[1],...,y[a]を考え
n=y[0]*10a+y[1]*10a-1+...+y[a]*1
とおく。
問題の例(n=1234)でいうと、
y[0]=1、y[1]=2、y[2]=3、y[3]=4、a=3となる。
このとき、次のようなアルゴリズムによって
（※）を満たすm,x[0],x[1],...,x[m]を構成することができる。
（１）まず、mをm≧a-1となるようにとる。
その後、z[0],z[1],...,z[m]の初期値として、下記のような値をとる。
・m-c＞aなら、z[c]=0である。
・m-c≦aなら、z[c]=y[c+a-m]である。
（２）c=0,1,...,m-1に対し、順次下記の操作によるx[c]の値の設定を行う。
・x[c]≦z[c]であるようにx[c]を取る。
そのあと、z[c+1]の値に(z[c]-x[c])*10を加える。
（３）（２）の操作終了後、x[m]=z[m]とする。
【アルゴリズムの証明】
アルゴリズムが停止することは明らかである（mに比例する計算量で計算が完了する）ので、ここではこのアルゴリズム により計算された答えが正しいことを示す。
（２）の操作をd回行ったとする。
・d=0ならば、これは初期値である。
m-c＞aであるならz[c]=0なので、z[c]*10m-c=0となる。
よって明らかに正しい答えを得る。
・d=e(1≦e≦m)ならば、帰納法の仮定により(e-1)回目までの操作では正しい答えが得られている。
すなわち、
x[0]*10m+x[1]*10m-1+...+x[e-1]*10m-e+1+z[e]*10m-e+z[e+1]*10m-e-1+...+z[m+1]*1=nである。
このとき、「古い」z[e+1]をoとおくと、
「新しい」z[e+1]はz[e+1]=o+(z[e]-x[e])*10を満たすので、
z[e]*10m-e+o*10m-e-1=x[e]*10m-e+z[e+1]*10m-e-1
が成り立っている。
よって、e回の操作でも正しい答えを得る。
また、この時、
(x[e]+z[e+1])-(z[e]+o)=9(z[e]-x[e])である。（＊）
以上により、アルゴリズムの正しさは示された。
（アルゴリズムの証明終わり）
（＊）より、１回の操作で、各位の総和は９の倍数だけ増加する。
したがって、アルゴリズムが停止したときも、開始前から総和が９の倍数だけ増加しているのは明らかである。
以上より、結論は示された。（証明終わり）
【感想】
数学というよりは、情報科学のような証明になってしまいました。
発想の大元は、(非負)整数a,b,c,dに対し、
a*10+b=c*10+dであるなら(c+d)-(a+b)は９で割り切れるということだけです。
きっちり書こうとしたらやたら冗長になってしまいました。
◆東京都 かえるさんからの解答。
１０００Ａ＋１００Ｂ＋１０Ｃ＋Ｄを１０００ａ＋１００ｂ＋１０ｃ＋ｄで書き換えたとする。
（文字は全て非負整数）
１０００Ａ＋１００Ｂ＋１０Ｃ＋Ｄ＝１０００ａ＋１００ｂ＋１０ｃ＋ｄ
⇔
（９９９＋１）Ａ＋（９９＋１）Ｂ＋（９＋１）Ｃ＋Ｄ
＝（９９９＋１）ａ＋（９９＋１）ｂ＋（９＋１）ｃ＋ｄ
→Ａ＋Ｂ＋Ｃ＋Ｄ≡ａ＋ｂ＋ｃ＋ｄ（ｍｏｄ９）
ゆえ、書き換えたあとの各位の総和と書き換えるまえの各位の総和の差は９で割り切れることが示された。
【証明了】
◆埼玉県 masaru2002さんからの解答。
例を用いれば、
1234=1000a+100b+10c+dで
a=10b=100c=1000d である。
a→b→c→dと数を移動させるとき必ず10倍される。
それらの数の和から元の数の和を引くのであるから必ず9の倍数になる。
(10-1は9,100-1は99,1000-1は999)
一般の場合も同じ。
◆大阪府 博士さんからの解答。
1234=a*1000+b*100+c*10+d*1と置いたとき、
書き換え前の式ではaが1、bが2であり、そこからaが1減るとbが10増える。
（c,dが変化しなければ）
この関係を、任意の数a''を使って
a=1-a''
b=2+a''*10
と表せる。
同様にbとcの関係をb''を使って表すと（a,dが変化しなければ）、
b=2-b''
c=3+b''*10
となる。cとdの関係も同様である。
これらの関係を組み合わせると、a,b,c,dの関係を任意の数a',b',c'を用いて以下のように表すことが出来る。
（aが減り、そのためbが増える、次にbを減らし、それによりcが増え…と順に考えれば、全ての場合に当てはまる）
a=1-a'
b=a'*10+2-b'
c=b'*10+3-c'
d=c'*10+4
この式を用いれば、書き換え後の各位の総和と書き換え前の各位の総和の差
a+b+c+dー(1+2+3+4)は、
a+b+c+dー(1+2+3+4) =1-a'+a'*10+2-b'+b'*10+3-c'+c'*10+4-(1+2+3+4) =(10-1)*a'+(10-1)*b'+(10-1)*c'+1+2+3+4-(1+2+3+4) =9*(a'+b'+c')+1+2+3+4-(1+2+3+4) =9*(a'+b'+c')となり、9で割り切れる。QED。