翻硬币问题

题目

总共有$n$枚硬币均正面朝上,规则规定每次只能将其中$p$枚硬币翻面($1≤p≤n$)。问最少需要多少次操作才能将所有硬币翻面。

思路

  • 先进行$n/p$次操作,将$(n/p - 1)*p$枚硬币翻面,令$r = n % p$,则剩余$r + p$;
  • 考虑将其中$x$枚反面朝上的硬币翻面,$p - x$枚正面朝上的硬币翻面;
  • 此时剩余正面向上的硬币总数为$x + r + p - (p - x) = p$,解方程得$x = (p - r) / 2$;
  • 方程有解的前提是$x$为偶数,故$p$和$r$应同奇偶,如$p$为奇数,每做一次操作,正面向上的硬币总数变换奇偶性
  • 现在讨论$n$和$p$的奇偶关系:
    • $n$为奇数,$p$为奇数:计$k$为$n/p$向上取整
      • $k$为奇数,可行
      • $k$为偶数,无解
    • $n$为偶数,$p$为偶数:可行
    • $n$为奇数,$p$为偶数:无解
    • $n$为偶数,$p$为奇数:计$k$为$n/p$向上取整
      • $k$为偶数,可行
      • $k$为奇数,无解
  • 应注意$n/p$介于1到2之间的情况。

答案

如满足上述奇偶讨论的要求:

  • 当$n/p$介于1到2之间时,答案为3;
  • 当$n/p$大于等于2时,答案为$n/p$向上取整;

不满足则无解。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×