沿数轴前进，拾或放硬币

isee

问题：数轴上每个整点处放好一枚硬币，正面朝上。开始时，小明站在原点，面向数轴正方向。
每一次操作如下：看一看所在位置的硬币。
(a)若硬币正面朝上，翻转这枚硬币。小明向后转，并前进1（个单位长）。
(b)若硬币反面朝上，拾起它，小明前进1。
(c)若该处没有硬币，小明放下1枚硬币，正面朝上，并前进1。
这样进行下去，直至有20枚硬币（不管在哪里）反面朝上。
问：一共进行了多少次操作？

zhcosin

我觉得编程计算比较好
还有啊，一开始的时候，是向前迈一步，还是先翻原点处的硬币并向负半轴转身？

kuing

回复 2# zhcosin

赶紧编一个，让俺学习下
按题意应该是先翻原点转身

To LZ：分类我建议选组合

zhcosin

回复 3# kuing

2. private static void coinProblem() {
3.                 int negativeCount = 0;        // 反面朝上的硬币数
4.                
5.                 // 整数位置与硬币状态的映射表，1 为正面，-1 为反面, 0 为没有硬币
6.                 Map<Integer, Integer> coinMap = new HashMap<Integer, Integer>();
7.                
8.                 int step = 0; // 步数
9.                 int pos = 0; // 当前位置
10.                 int direction = 1; // 前进方向, 1 - 正半轴， -1 - 负半轴
11.                 while (true) {
12.                         ++step; // 步数增1
13.                        
14.                         // 为避免保存无限长数组，采用哈希表保存硬币状态， 不在表中时就立刻加入.
15.                         Integer coinAtPos = coinMap.get(pos);
16.                         if (coinAtPos == null) {
17.                                 coinAtPos = 1;
18.                                 coinMap.put(pos, coinAtPos);
19.                         }
20.                        
21.                         if (coinAtPos == 1) {
22.                                 coinMap.put(pos, -1); // 翻转硬币
23.                                 direction *= -1; // 改变前进方向
24.                                 ++negativeCount;        // 反而朝上的硬币数目加1
25.                         } else if (coinAtPos == -1) {
26.                                 coinMap.put(pos, 0); // 拾起硬币
27.                                 --negativeCount;        // 反而朝上的硬币数目减1，之前少写了这里.
28.                         } else {
29.                                 coinMap.put(pos, 1); // 放下一枚硬币，正面朝上
30.                         }
31.                        
32.                         // 当反面朝上的硬币数目达到20时，结束.
33.                         if (negativeCount == 20) {
34.                                 System.out.println("step=" + step + ", pos=" + pos);
35.                                 return;
36.                         }
37.                        
38.                         pos += direction; // 前进一步
39.                 }
40.         }
41. }

Copy the Code

输出: step=51, pos=-2，即需要51步，此时位置在-2处.

kuing

回复 4# zhcosin

不愧是码农

isee

回复 4# zhcosin


    很遗憾，输出的结果，若是51次，则不正确。

PS:我认真字字的检查了主楼题目，我抄写的是正确的。

isee

我觉得编程计算比较好
还有啊，一开始的时候，是向前迈一步，还是先翻原点处的硬币并向负半轴转 ...
zhcosin 发表于 2017-9-6 17:19

    第一次操作：翻转原点处的硬币。向后转身，并前进一步。（到达数轴的-1处并面向数轴负方向）

    第二次操作：将（-1处的）硬币翻转。向后转身，并前进一步。（到达数轴的0处并面向数轴正方向）

    第三次操作：将原点处的硬币拾起，并向进一步。

   ……

kuing

俺也编了一个程，在 MMC 下。

1. Clear["Global`*"];
2. xo = 11;(*初始位置*)
3. n = 20;(*总长*)
4. x = xo;
5. v = 1;(*方向*)
6. fy = 0;(*-1个数*)
7. j = 0;(*操作次数*)
8. Do[a[i] = 1, {i, n}]
9. lst[j] = Table[a[i], {i, n}];
10. While[fy < n,
11. {j++;
12.   If[a[x] == 1,
13.    {a[x] = -1; fy++; v = -v;},
14.    If[a[x] == -1,
15.     {a[x] = 0; fy--;},
16.     {a[x] = 1;}]
17.    ];
18.   x = x + v;
19.   lst[j] = Table[a[i], {i, n}];
20.   }]
21. {j, x, v}(*输出最终操作次数、位置、方向*)
22. Table[lst[t], {t, 0, j}] // MatrixForm(*列出具体变化*)

Copy the Code

得出结果是：
{6098, 11, 1}
也就是说操作次数是 6098 次，而且操作完成后又回到了原来的地方，方向也向正
本来我还列出了具体变化表，但由于太大了，这里贴不了……

kuing

要列出来的话，改小一半吧，10个反面，结果为166。

为了更直观地观察，将数字变成有色圆，代码如下。

1. Clear["Global`*"];
2. xo = 6;(*初始位置*)
3. n = 2 xo - 2;(*总长*)
4. x = xo;
5. v = 1;(*方向*)
6. fy = 0;(*-1个数*)
7. j = 0;(*操作次数*)
8. Do[a[i] = 1, {i, n}]
9. ball[1] = Graphics[{Red, Disk[]}, ImageSize -> 10];
10. ball[-1] = Graphics[{Blue, Disk[]}, ImageSize -> 10];
11. ball[0] = Graphics[{LightGray, Disk[]}, ImageSize -> 10];
12. lst[j] = Map[ball, Table[a[i], {i, n}]]~Join~{j};
13. While[fy < n,
14. {j++;
15.   If[a[x] == 1,
16.    {a[x] = -1; fy++; v = -v;},
17.    If[a[x] == -1,
18.     {a[x] = 0; fy--;},
19.     {a[x] = 1;}]
20.    ];
21.   x = x + v;
22.   lst[j] = Map[ball, Table[a[i], {i, n}]]~Join~{j};
23.   }]
24. {j, x, v}(*输出最终操作次数、位置、方向*)
25. Table[lst[t], {t, 0, j}] // MatrixForm(*列出具体变化*)

Copy the Code

输出的变化如下，其中红色正面，蓝色反面，灰色为空：

kuing

通过观察规律，猜测：使 $2k$ 个反面的操作次数为 $3\cdot2^{k+1}-4k-6$。

isee

回复 8# kuing


    操作次数是 6098 次，bingo!

kuing

通过观察规律，猜测：使 $2k$ 个反面的操作次数为 $3\cdot2^{k+1}-4k-6$。
kuing 发表于 2017-9-7 01:17

证明：
设 $f(n)=3\cdot2^{n+1}-4n-6$。

命题：操作 $f(n)$ 次后，区间 $[-n,n-1]$ 内的 $2n$ 枚硬币为反面朝上，过程中区间以外的硬币不会触碰到，操作完后小明回到原点且面向数轴正方向。

实操知 $n=1$ 时命题成立。

假设当 $n=k$ 时命题成立，实操易知，在此假设的情况下，再经 $4k+2$ 次操作，情况必变成：$x=-(k+1)$ 和 $x=k$ 两处的硬币为反，之间的全变回正，之外的也不会触碰到，操作完又回到原点且面向正方向。

这样，介于这两处之间的部分就和最初一样，故由归纳假设，再经 $f(k)$ 次操作，便使区间 $[-(k+1),k]$ 内的都为反，整个过程中此区间外的硬币不会触碰到。

而经计算易知 $f(k)+4k+2+f(k)=f(k+1)$，所以当 $n=k+1$ 时命题成立，故由数学归纳法知命题对 $n\inN^+$ 成立。

所以，对于原题，结果就是 $f(10)=6098$。


如果觉得上述过程不好理解，请看下面的图解：

abababa

还以为发了解答，打开一看竟然是这个

kuing

回复 13# abababa

isee

回复 13# abababa


     m大一直很幽默

kuing

更新了一下9#，添加了行号。

isee

回复 10# kuing


    数感太好了，这都能猜测出来。。。那把奇数情形也猜猜吧。。。


PS：不对啊，起这么早~~~

kuing

数感太好了，这都能猜测出来。。。那把奇数情形也猜猜吧。。。

PS：不对啊，起这么早 ...
isee 发表于 2017-9-7 09:19

奇数？不就是偶数的前一步么？

回PS：起早是被蚊子吵醒了，不过平时的话会睡回去，今天醒了之后用手机上论坛，看着那图突然想到了证明，就起来写了。

可以说这证明完全是靠电脑辅助，若是没电脑我估计都不敢撸。

PS：无论怎么看，这题都没有“函数”的东西，再次建议分类为“组合”。

zhcosin

回复 6# isee
原来代码有 bug，在遇到反面硬币拾起它后，忘了将反面硬币总数减一，修改后输出结果 step=6098, pos=-1, direction=1，即要6098步，此时位置在-1处，面向正方向.

kuing

回复 19# zhcosin

噢，原来你的代码是到 20 个反面之后就停了，虽然方向也已经改变，但没向前走，所以最终停在-1处……
我的是20个时还会走一步，所以回到原点。