Re: Do you know "Lights-Out"?

Article View: fj.sci.math

Article #14178

#14178

From: Yoshimasa Kimura
Date: Fri, 24 Nov 1995 00:00

23 lines
1667 bytes

In article <DIHCMF.Dv4@rdsun26.roland.co.jp>
 kusakabe@roland.co.jp (Satoshi Kusakabe) wrote:
>１、つぎの命題は正しいでしょうか。
>　2^25 通りの点灯パターンは、すべてこのゲームの初めのパターンになりうる。
>　私は正しいと思いますがまだきちんと証明していません。

私も、このゲームを見たとき(テレビ番組で紹介されていた)にちょっと考え
てみたんですが、結論からいうとこの命題は成立しません。25個のボタンの
うちいくつか(1つ以上)を選んでそれぞれを1回ずつ押したとき、初期状態に
戻ってしまうような組合せが少なくとも1つ(実際には3つ)あるからです。


>２、任意の（解ける）パターンが与えられたとき、最小手数をもとめる
>簡単なアルゴリズムはあるか。

こちらの方は示してしまうとゲームとしての面白みが消失してしまうので
割愛します。
--
 ＿＿＿
｜    ｜ nmi@cs.titech.ac.jp
｜Ｎ  ｜ 東京工業大学 大学院 理工学研究科
｜ み ｜ 情報工学専攻 徳田研究室 博士後期課程 木村喜昌
 ￣￣￣

Technical Details

Message-ID: <xocn39muoah.fsf@marimo.cs.titech.ac.jp>

Path: arc1-ca.pugleaf.net!unknown!not-for-mail

References: <DIHCMF.Dv4@rdsun26.roland.co.jp>

Show Full Headers

Complete Article Headers

X-Google-Language: Japanese,JIS
X-Google-Thread: f4956,1d9f7ee0b1d9a7c7,start
X-Google-Attributes: gidf4956,public
From: nmi@cs.titech.ac.jp (Yoshimasa Kimura)
Subject: Re: Do you know "Lights-Out"?
Date: 1995/11/24
Message-ID: <xocn39muoah.fsf@marimo.cs.titech.ac.jp>
X-Deja-AN: 120108214
distribution: fj
sender: nmi@marimo.cs.titech.ac.jp
references: <DIHCMF.Dv4@rdsun26.roland.co.jp>
content-type: text/plain; charset=ISO-2022-JP
organization: Dept. of Comp. Sci., Tokyo Inst. of Tech., JAPAN
mime-version: 1.0
newsgroups: fj.sci.math

Reply to Parent Message