参加型ナゾトキサイト『クイズ大陸』で、脳トレをどうぞ！

FAQ

RSS
@quiz_tairikuさんをフォロー

割り切れないなあ。

難易度：★★ 　

河野真衣 2012/01/12 15:35

明後日からセンター試験が始まるようで受験生の皆さんは大変ねえと思っていたら、ひよっと問題が浮かびました。
x,yを自然数としたとき、xで割っても、x^2で割っても余りが1になるようなyは当然ながらいくらでもあります。例えば、x=4,y=17、x=5,y=26 等。しかし、xで割ると余りが1になり、x^2で割ると余りが2になるようなyはありません。そこで問題です。

「問題」 x,yは自然数です。このとき、
(1) xで割ると余りが1になり、(x^2+1)で割ると余りが2になるような数をyとして、x,yの組を1つ見つけてください。
(2) xで割ると余りが1になり、(x^2+1)で割ると余りが2になり、(x^3+2)で割ると余りが3になるような数をyとして、x,yの組を1つ見つけてください。




	【答えの1例 (1) x=2,y=17 17=8×2+1=3×(2^2+1)+2 (2) x=3,y=322 322=107×3+1=32×(3^2+1)+2 =11×(3^3+2)+3 】

回答募集は終了しました。

▲ △ ▽ ▼ No.1

(1)x=2,y=7
(2)x=3,y=322

けんぎ 2012/01/12 16:53

手計算ではこのくらいがやっと

河野真衣手計算お疲れ様でした。(1)(2)共正解です。

▲ △ ▽ ▼ No.2

(1)
mod(y,x)=1
mod(y,x^2+1)=2
mod(y,x^2)=1

mod(17,4)=1
mod(17,16)=1
mod(17+16,4)=1
mod(17+16,16)=1

mod(17+16+16,16+1)=15
mod(17+16+16+16,16+1)=14
mod(17+16*4,16+1)=13
・
・
・
mod(17+16*15,16+1)=2…これが答え→x=4,y=257
mod(17+16*16,16+1)=1
mod(17+16*17,16+1)=0
x=4,y=257…(1)の答え
(2)
ギブアップ
計算機では下のようになる。
x=4,y=597…(2)の答え

計算機君の答え
(1)
1000 LET t0=TIME
1100 INPUT n
1200 PRINT "n;y,x,x^2+1"
1300 FOR x=1 TO n
1400 FOR y=1 TO n^2*2
1500 IF MOD(y,x)=1 THEN GOTO 1700
1600 IF MOD(y,x)><1 THEN GOTO 2000
1700 IF MOD(y,x^2+1)=2 THEN GOTO 1900
1800 IF MOD(y,x^2+1)><2 THEN GOTO 2000
1900 PRINT n;y;x;x^2+1
2000 NEXT y
2100 NEXT x
2200 PRINT "xの範囲1<x<n、yの範囲1<y<2*n^2の検索に要した時間"
2300 PRINT TIME-t0;"秒かかりました"
2400 END

(2)
1000 LET t0=TIME
1100 INPUT n
1200 PRINT "n;y,x,x^2+1;x^3+2"
1300 FOR x=1 TO n
1400 FOR y=1 TO n^3*2
1500 IF MOD(y,x)=1 THEN GOTO 1700
1600 IF MOD(y,x)><1 THEN GOTO 2200
1700 IF MOD(y,x^2+1)=2 THEN GOTO 1900
1800 IF MOD(y,x^2+1)><2 THEN GOTO 2200
1900 IF MOD(y,x^3+2)=3 THEN GOTO 2100
2000 IF MOD(y,x^3+2)><3 THEN GOTO 2200
2100 PRINT n;y;x;x^2+1;x^3+2
2200 NEXT y
2300 NEXT x
2400 PRINT "xの範囲1<x<n、yの範囲1<y<n^3*2の検索に要した時間"
2500 PRINT TIME-t0;"秒かかりました"
2600 END

十進BASICにて実行すると吉。

un 2012/01/12 21:19

いつも長い答えですみません。 (・o・∥)

河野真衣新年早々力作をいただき有難うございます。(1)(2)共正解です。
計算機君にお年玉を上げて下さいね。

▲ △ ▽ ▼ No.3

(1)x=2,y=7
(x=2,x^2+1=5→7÷2=3…1,7÷5=1…2)
(2)x=3,y=322
(x=3,x^2+1=10,x^3+2=29→
322÷3=107…1,322÷10=32…2,
322÷29=11…3)

４０１３ 2012/01/21 08:20

これで

河野真衣 (1)(2)共正解です。(2)は簡単に見付かりましたか?

▲ △ ▽ ▼ No.4

河野真衣 2012/01/25 10:42

答えを書いておきます。
(1)(x,y)=(m,m^3-m^2+m+1) 　mは2以上の自然数。
　　［ m^3-m^2+m+1=m(m^2-m+1)+1=(m^2+1)(m-1)+2 ］
(2)(x,y)=(3,322),(4,597),(5,1146)
(1)のように一般式で表そうとするとえらく複雑になりそうなのでこれは諦め、式をこね回して3例だけ挙げました。誰か一般式で表せられる人がいたら書き込んでください。

▲ △ ▽ ▼ No.5

vipper 2012/01/28 14:53

３以上のある整数 x に対して問題(2)を満たすような最小の y は、

y ＝ {f(x) * (x^3 + 2) + 60} * x * (x^2 + 1)/(10 * (x - 2))　＋ (x^4 + 2x^3 + 2x + 1)

x mod 10 = 0 or 5　のとき　f(x) ＝　2 * (x - 5)
x mod 10 = 1 or 6　のとき　f(x) ＝　2 * (2x - 7)
x mod 10 = 2 or 7　のとき　解なし
x mod 10 = 3 のとき　f(x) ＝ 2 * (3x - 9)
x mod 10 = 4 のとき　f(x) ＝ 3x - 12
x mod 10 = 8 のとき　f(x) ＝ x - 8
x mod 10 = 9 のとき　f(x) ＝ 2 * (4x - 11)
(a mod b は、a を b で割ったときの余り。)

と書けると思われます。(x^2 + 1) と (x^3 + 2) は、[x = (5n + 2) : nは非負整数] のとき、共に５の倍数となって解がなくなります。また、x と (x^3 + 2) は、x が奇数であれば互いに素ですが、x が偶数であれば共に２の倍数となり若干状況が違ってきます。
従って、x = 10n + 1 , 10n + 2 , 10n + 3 , … と場合分けをすることにより問題を解いています。場合分けをしないでスッキリ纏めることが出来るかどうかは解かりません。

また x が奇数であれば上述の式に、x * (x^2 + 1) * (x^3 + 2) を加えていった値も題意を満たします。x が偶数であれば x * (x^2 + 1) * (x^3 + 2) / 2 を加えていった値が題意を満たします。そして題意を満たすような(x , y)の組み合わせは、これ以外に存在しないはずです。
以下にVBAプログラムで総当たり的に解を求めた結果を貼っておきます(x = 31 まで)。以下の数値と上に挙げた式が一致することを確認済みです。
x ＝ 3 のとき y ＝ 322 x ＝ 4 のとき y ＝ 597 x ＝ 5 のとき y ＝ 1146 x ＝ 6 のとき y ＝ 14173 x ＝ 8 のとき y ＝ 5657 x ＝ 9 のとき y ＝ 394012 x ＝ 10 のとき y ＝ 139281 x ＝ 11 のとき y ＝ 614516 x ＝ 13 のとき y ＝ 2684982 x ＝ 14 のとき y ＝ 1938679 x ＝ 15 のとき y ＝ 1820206 x ＝ 16 のとき y ＝ 6093729 x ＝ 18 のとき y ＝ 2251927 x ＝ 19 のとき y ＝ 36232944 x ＝ 20 のとき y ＝ 10874721 x ＝ 21 のとき y ＝ 31892512 x ＝ 23 のとき y ＝ 85073482 x ＝ 24 のとき y ＝ 52580281 x ＝ 25 のとき y ＝ 42958626 x ＝ 26 のとき y ＝ 116524565 x ＝ 28 のとき y ＝ 37782837 x ＝ 29 のとき y ＝ 463989996 x ＝ 30 のとき y ＝ 131202721 x ＝ 31 のとき y ＝ 338001588

▲ △ ▽ ▼ No.6

河野真衣 2012/01/28 22:48

vipperさん、丁寧な回答有難うございました。
x=3,4,5,6……に対して題意を満たすyが存在しそうだなとは思っていましたが、ほぼ予想が当たっていました。ただ、x=2,12,22と7,17,27に適解が無いのはなにか不思議な気がします。これでいくとx=32,37,42,47にも解が無さそうですね。

▲ △ ▽ ▼ No.7

vipper 2012/01/29 00:25

＞河野様
x＝32,37,42,47…　にも解は無いですね。何故無いのかは、実際に (x^2 + 1) と (x^3 + 2) へ [5n + 2] (2,7,12,17…) を代入してみれば証明するのは容易です。代入すると、

x^2 + 1 ＝ (25n^2 + 20n + 5) ＝ 5*(5n^2 + 4n + 1)
x^3 + 2 ＝(125n^3 + 150n^2 + 60n + 10) ＝ 5*(25n^3 + 30n^2 + 12n + 2)　です。

y は x^2 + 1 で割ったときの余りが 2 でしたので、
y ＝ 5*(5n^2 + 4n + 1)*A ＋ 2 (Aは非負整数) … ①　と表せる必要があります。
また、x^3 + 2 で割ったときの余りが 3 でしたので、
y ＝ 5*(25n^3 + 30n^2 + 12n + 2)*B ＋ 3 (Bは非負整数) …②　と表せる必要があります。

ところで ① は y = [5の倍数] + 2 ですが ② は y = [5の倍数] + 3　となっていますので、①と②は同時に成立し得ません。従って、 x = 5n + 2 のときに解は存在しないことになります。

ちなみに x = 5n + 2 (2,7,12,17…) でなければ、(x^2 + 1) と (x^3 + 2) は必ず互いに素になります。またこの場合には必ず条件を満たすような y が存在します。ここら辺は不思議かもしれません。
ここを証明しようと思うと、「ユークリッド互除法」や「中国の剰余定理」を理解していないとなかなか難しいように思います。興味がありましたら一度調べてみて下さい。

▲ △ ▽ ▼ No.8

河野真衣 2012/01/29 15:47

vipperさん、重ねてご教示有難うございます。x=5n+2のとき、条件に合うyが存在しないことがよく判りました。ここまで深くは考えておりませんでしたので、大変参考になりました。

このクイズのヒント

ヒント知らないよ

このクイズの参加者（4人）

ジャンル・キーワード

携帯用ページ

携帯電話のQRコード読み取り機能でこのページを見られます。

広告お買い物は下記のリンクからどうぞ

楽天市場はこちらから
Amazonはこちらから

広告
クイズ大陸関連書籍