香烟问题

APPSYZY

假设有$n$根香烟，每吸$1$根香烟会产生$1$个烟头，每$k(k>1)$个烟头又可以卷成一根新的香烟，问一共可得几根香烟（包括原来的$n$根在内）？

kuing

O(∩_∩)O哈！我记得这类题以往是用蜡烛来表达的，看来因为现在的小朋友未必知道蜡烛是啥，就改成香烟了

APPSYZY

回复 2# kuing

战巡

回复 1# APPSYZY


我咋记得以前一般是买饮料，k个空瓶换一瓶新的...

设$n$表示为$k$进制有p位，各位为$a_0,a_1,...,a_{p-1}$，$0\le a_i<k$，也就是
\[n=a_{p-1}k^{p-1}+a_{p-2}k^{p-2}+...+a_1k+a_0\]
那么第一轮下来，可再生出的数量为
\[a_{p-1}k^{p-2}+a_{p-2}k^{p-3}+...+a_1\]
，同时还剩下$a_0$个
第二轮下来，可再生的数量为
\[a_{p-1}k^{p-3}+a_{p-2}k^{p-4}+...+a_2\]
还剩下$a_0+a_1$个
以此类推，最后总数会是
\[a_{p-1}\sum_{i=1}^pk^{p-i}+a_{p-2}\sum_{i=2}^pk^{p-i}+...+a_1(k+1)\]
但最后剩下$a_0+a_1+...+a_{p-1}$个，回头还要对这个继续上面的处理，令$n_1=a_0+a_1+...+a_{p-1}$，再走一遍上面的程序，直到最后剩余的数量小于$k$

APPSYZY

回复 4# 战巡
网上找到的博客里的“一般性结论”，试了三组数，都是对的，不知道咋来的
blog.sina.com.cn/s/blog_804164070101prua.html

realnumber

也记得是饮料，k个空瓶换一瓶新的
觉得从方程角度理解就可以解决了
1瓶饮料=1饮料+1空瓶，简写为x=y+z
kz=x,问nx=ty(特别过程中空瓶不够 ，可以借1个空瓶，归还1个空瓶)
求t
t=[kn/(k-1)]

--没注意到条件，不能借

APPSYZY

答案应该是$n+\lfloor(n-1)/(k-1)\rfloor$

hbghlyj

APPSYZY 发表于 2019-7-20 23:46
回复 4# 战巡
网上找到的博客里的“一般性结论”，试了三组数，都是对的，不知道咋来的
blog.sina.com.cn/s/blog_804164070101prua.html

系统维护中，博文仅作者可见。登陆后可查看本人文章。