アットランダム≒ブリコラージュ

11151：3a+5bで表せない最大数…(a,bは自然数)...

問題11151・・・http://www004.upp.so-net.ne.jp/s_honma/relax/sum10.htm より 引用(改変 ^^)

Orz〜

３ａ＋５ｂ (ただし, a, b は 自然数) の形で表わせない自然数の最大値を求めよ。

解答

・わたしの…

非負整数のときが…

(3-1)(5-1)-1=7 なので…

3(a+1)+5(b+1)=3a+5b+8

so…

7+8=15 

が、表せないMaxですね ^^

11150：ax+by+czで表せない最大の数...

問題11150・・・http://www004.upp.so-net.ne.jp/s_honma/relax/sum10.htm より 引用 Orz〜

自然数 ａ、ｂ、ｃ の最大公約数は１であるとする。

０以上の整数 ｘ 、 ｙ 、ｚ を使って、ａｘ＋ｂｙ＋ｃｚ　の形で表せない最大の整数を求めよ。

解答

・わたしの…

a<b<c とする…

ax+by・・・(a-1)(b-1)以上は表せるので…

(b-1)(c-1)-1が(a-1)(b-1)以上なら表せないMaxは…(a-1)(b-1)-1

(b-1)(c-1)-1-(a-1)(b-1)

=(b-1)(c-a-2)-1>=0 ならいい…

c>a+2 ならいいけど…

a<b<c なので…c>a+2 と担保されているので…

けっきょく…

表せないMax=(a-1)(b-1)-1

ですよね…?

↑

嘘っぱちでしたわ…^^; Orz…

↓

・鍵コメT様からのコメント Orz〜

c=am+bn (m,nは負でない整数)の場合は，(a-1)(b-1)-1でよいのですが，
そうでない場合を含めた一般的な式を得るのはとても難しいと思います．

そもそも，「a,b,cの最大公約数が1」はa,bが互いに素であることは保証せず，
a,bだけでは表されない自然数が無数にある可能性もあります．
(例: a=6,b=10,c=15のとき，a,bだけでは奇数は表せません．
この場合は，30以上の整数はすべてax+by+czの形で表すことができます．)

a,bが互いに素であったとしても，a,bだけでは表されない(a-1)(b-1)-1が，
cも用いることで表される場合もあります．
(例:a=5,b=9,c=17のとき，31はa,bだけでは表せませんが，
cを用いれば，a+b+cのように表されます．
この場合は，22以上の整数はすべてax+by+czの形で表すことができます．)

*時間あるときに…

6,10,15 のときと…

5,9,17 のときがそうなることを考えてみよっと ^^;v

*血圧絡みの記事を探してたんですが...自分ではアップしてたと思うのに…

いつのまにか消えてるとしか思えない…^^;;;…あかんですよ…yahooさん!!

猶予期間を設けて下さってれば...別にアーカイブスできてたのに…!!

線形結合…^^;

よく出る問題なんだけどその背景がすぐわからず…^^;

 http://www004.upp.so-net.ne.jp/s_honma/relax/sum10.htm ;より 引用 Orz〜

「『ａ 、 ｂ を互いに素な自然数とする。０以上の整数 ｘ 、 ｙ を使って ａｘ＋ｂｙ の形で表すことができない最大の整数を求めよ。』

 

 

（証明）　

ｂ＞ａ として考える。0以上の整数 ｘ、ｙ を使って、ａｘ＋ｂｙ の形で表される数の集合

 

をＡとする。１から順に ｂ 個毎に行を変えながら ａｂ まで書く。

 

　　1　　 2　　3　 …　　b

　 b+1　 … 　… 　… 　2b

　 ・　　　　　　　　　 ・

　 ・　　　　　　　　　 ・

　 ・　　　　　　　　　 ・

(a-1)b+1 … 　… 　… 　ab

 

a の倍数に着目したとき、a の倍数は各列1つしか現れない。

 

実際に、任意の列　ｋ、ｂ＋ｋ、２ｂ＋ｋ、・・・、（ａ−１）ｂ＋ｋ　

（ｋは自然数で、１≦ｋ≦ｂ）において、ある自然数 ｍ、ｎ （１≦ｍ＜ｎ≦ａ）が存在して、　

ｍｂ＋ｋ≡ｎｂ＋ｋ　（ｍｏｄ　ａ）　が成り立つと仮定すると、

 

（ｍ−ｎ）ｂ≡０　（ｍｏｄ　ａ）　で、（ａ，ｂ）＝１　より、　

ｍ−ｎ≡０　　（ｍｏｄ　ａ）　となる。

 

しかるに、これは、　１≦ｍ＜ｎ≦ａ　に矛盾する。

 

したがって、ａ個の任意の列　ｋ、ｂ＋ｋ、２ｂ＋ｋ、・・・、（ａ−１）ｂ＋ｋ　の各項を ａ で割った余りは全て異なる。

このとき、この列の項で、ａ で割り切れるものがただ一つ存在する。

 

右端の列、即ち、ｂ で割り切れる数はすべてＡに入っている。

それ以外の列は、どこかでａ の倍数が現れ、それ以後はすべてＡに入る。

 

ａ の倍数は各列1つしか現れないので、最後にＡに含まれる列は、ａ(ｂ−１) が含まれる列

 

なので、表すことの出来ない最大の数は、その１行前の数字 ａ(ｂ−１)−ｂ＝ａｂ−ａ−ｂ　と

 

なる。（証終）

 

『ａ、ｂ を互いに素な自然数とする。０以上の整数 ｘ、ｙ を使って ａｘ＋ｂｙの形で表すことができない自然数の個数を求めよ。』

 

（解）　ａ、２ａ、３ａ、・・・、（ｂ−１）ａ　の各数を ｂ で割った余りは、１、２、３、・・・、ｂ−１ の何れかで、互いに１対１に対応する。このとき、求める場合の数は、

 

［｛ａ＋２ａ＋３ａ＋・・・＋（ｂ−１）ａ｝−｛１＋２＋３＋・・・＋（ｂ−１）｝］/ｂ

 

　＝（ａ−１）｛１＋２＋３＋・・・＋（ｂ−１）｝/ｂ

 

　＝（ａ−１）（ｂ−１）/２

 

で与えられる。

 

したがって、ａｘ＋ｂｙ の形で表すことができない自然数の個数は、

 

　　　　　　　(a-1)(b-1)/2

11149：ニュートン算…ポンプ…^^

問題11149・・・浮浪さんのサイト http://homepage1.nifty.com/Hagure/ 「浮浪の館」より Orz〜

解答

正にシンクロニシティ!!

ライブ問にてまたいずれ ^^