20階建てで一階あたり20室あるホテルで以下のルールで部屋番号を設定すると、最大になるのは何号室?

20階建てで一階あたり20室あるホテルで以下のルールで部屋番号を設定すると、最大になるのは何号室?

1.部屋連番。例:1階の最初の部屋は1号室

2.4と9のついた数字を飛ばす。

解答:

10あたりの飛ばさない数は

12356780

となり、8個となる。

100までに飛ばさない数は上記の8個*10となるが、40番台と90番台は飛ばすので、

8*8=64個

となる。

400を64で割ると、400/64=6あまり16

つまり、6回100の位が変化する。

そして、400番台は全て飛ばすので、6回変化するという事で700番台となる。

そして先ほどのあまりの16までに、登場する抜け番は

10あたりの飛ばさない数は前述の通り8個なので

16/8で2あまり無しとなり、

720番が最大となる。

よって最大の部屋番号は720号室となる。

Share

以前のパズル:nまでの整数を二つの組に分けて合計した結果が同じだった2番目と3番目を出力するで見つけた式は隣接三項間漸化式という事が分かった

数式にするとこんな感じ?勉強していないので表記が間違っているかもしれませんが・・・

N¥tiny kを任意の整数とし

N¥tiny 0¥large =-1

N¥tiny 1¥large =0

としたとき、

N¥tiny k+1¥large=N¥tiny k ¥large 6-(N¥tiny k-1 ¥large -2)

となる。

パズル:nまでの整数を二つの組に分けて合計した結果が同じだった2番目と3番目を出力する その2 – NAL-6295の舌先三寸

で見つけた式は隣接三項間漸化式という事がわかった。(多分。)

という事は、この漸化式から一般解が導ければ、その後、数学的帰納法で証明することが可能という事か?

#まだ、続いていたのか。という話題。

Share

最大公約数を算出するためのユークリッドの互除法

2 つの自然数(または整式) a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

ユークリッドの互除法 – Wikipedia

素因数分解しなくても、ユークリッドの互除法という方法を使えば、もっと早く算出できるという事がわかった。

というか、読んだから分かったんだけど。

20と12なら

20/12 = 1あまり8

12 / 8 = 1 あまり 4

8 / 4 = 2 あまり 0

で4が最大公約数となる。

これは、便利な方法だ。

Share

ある整数xとyの最大公約数を出す時の法則を見つけた

前回のエントリで最小公倍数を出す法則を見つけたが、その過程で最大公約数を出している事が分かった。

xとyの素因数リストの中にある重複部分を掛けた結果が最大公約数。

重複した部分が無い場合は1が最大公約数。

xとyをそれぞれ素因数分解して、xの素因数リストとyの素因数リストを出し、

xの素因数リストとyの素因数リストの重複部分を打ち消し、

残ったxの素因数リストを乗算して算出した値にyを掛けると、

xとyの最小公倍数になる。

例:

xが12でyが20の時、

xの素因数が2,2,3

yの素因数が2,2,5

重複部分を打ち消しあうと

xの素因数の残りが3

yの素因数の残りが5

yにxの素因数の残りを掛けると60

(ついでに)xにyの素因数の残りを掛けても60

ある整数xとyの最小公倍数を出す時の法則を見つけた – NAL-6295の舌先三寸

上記例を使うと、

xの素因数 2,2,3とyの素因数 2,2,5のうちの重複部分である、

2,2

をかけると、4となり、

12と20の最大公約数は4である。

となる。

Share

ある整数xとyの最小公倍数を出す時の法則を見つけた

ある整数xとyの最小公倍数を出す計算をして結果を眺めていたら、ある法則がある事がわかった。

xとyをそれぞれ素因数分解して、xの素因数リストとyの素因数リストを出し、

xの素因数リストとyの素因数リストの重複部分を打ち消し、

残ったxの素因数リストを乗算して算出した値にyを掛けると、

xとyの最小公倍数になる。

例:

xが12でyが20の時、

xの素因数が2,2,3

yの素因数が2,2,5

重複部分を打ち消しあうと

xの素因数の残りが3

yの素因数の残りが5

yにxの素因数の残りを掛けると60

(ついでに)xにyの素因数の残りを掛けても60

12と20の最小公倍数は60

無知ゆえの発見が楽しい。

#ちなみに、やっと数学的帰納法の意味がわかりました。

Share