熄燈問題的一般化


4

here中查找原始問題。

讓集合 $ J $ 為正整數對的集合 $(m,n)$ $ m \ ge n $

假設 $(m,n)\ in J $ 。然後有 $ m $ 燈,它們最初是關閉的。您選擇 $ n $ 燈的每一步,然後更改其狀態。假設 $ f:J \ rightarrow \ mathbb {N} $ 為一個函數,這樣,如果有一種方法可以在有限的步驟中點亮所有燈,那麼 $ f(m,n)$ 是最小步驟數。如果我們無法在有限的步驟中執行此操作,則 $ f(m,n)= 0 $ 。我對 $ f(m,n)$ 的值感興趣。這是我的主要結論:如果 $ m $ 為奇數且 $$ f(m,n)= 0 $$ =" math-container"> $ n $ 是偶數。 $$ f(m,n)= 3 $$ 如果 $ m $ $ n $ 是相同的奇偶校驗, $ m \ ne2n $ $ m>n \ ge \ frac m3 $ 。如果 $ m = n $ (顯而易見),則 $$ f(m,n)= 1 $$

有人可以幫我解決這個難題嗎?

1

Very fun puzzle.

I'll start with the obvious cases:

  • If m is odd, n is even:

  • If m=n:

  • If n is a factor of m:

Now the harder cases. Let me define some terms:

  • a=m%n (aka the amount of lights left after just turning sets of n on until u can't)
  • b: an arbritary number >a. You will eventually reach the point where you have a string of on lights and then a off lights. You switch the state of n lights as usual. When this happens, b is the number of lights that were on that you turn off.

The strategy is to manipulate the lights such that there are n lights off. Mathematically, this means that n=a+b-(n-b).

Simplifying this equation gives you n=a/2 +b. Remember that a, b, & n are all integers. So long as a is even, this equation can always work out,except in cases already highlighted above. This poses a problem if a is odd, and in that case you cannot create n off lights in one step. What you can do is make the number of off lights even, making a even for the next round.

And finally:

This was a good puzzle, thanks.


1

Let $q$ be the integer result of dividing $m$ by $n$, and $r$ the remainder of this division. So $m=qn+r$ with $0\le r < n$, and $q$ is the whole number $q=\lfloor\frac{m}{n}\rfloor$.

If you just flip $n$ lights on at a time, after $q$ moves you would have just $r$ lights left. There are a few different cases to consider.

$r=0$:

$r+n$ is even, and $q\ge2$.

$r$ is even

$r$ odd, $n$ even (i.e. $m$ odd, $n$ even )

$r$ odd, $n$ odd, $q=1$. This is the trickiest case.

Here is a pictorial view of the various cases: