每日一题[942]砝码称重

给定正整数$n$,已知用克数都是正整数的$k$块砝码和一台天平,可以称出质量为$1,2,3,\cdots,n$克的所有物品.求$k$的最小值$f(n)$.


分析与解 设这$k$块砝码的质量数分别为$a_1,a_2,\cdots,a_k$,且
$$1\leqslant a_1\leqslant a_2\leqslant \cdots\leqslant a_k,\ a_i\in\mathbb{Z},\ i=1,2,\cdots,k.$$因为天平两端都可以放砝码,故可称质量为\[\displaystyle\sum_{i=1}^{k}x_ia_i,\]其中$x_i\in\{-1,0,1\}$,$i=1,2,\cdots,k$.若利用这$k$块砝码可以称出质量为$1,2,3,\cdots,n$的物品,则上述表示式中含有$1,2,3,\cdots,n$,由对称性易知也含有$0,-1,-2,\cdots,-n$,即\[\left\{0,\pm 1,\pm 2,\cdots,\pm n\right\}\subseteq
\left\{\left.\displaystyle\sum_{i=1}^{k}x_ia_i\,\right|x_i\in\{-1,0,1\},\ i=1,2,\cdots,k\right\}.\]所以\[2n+1\leqslant \left|\left\{0,\pm 1,\pm 2,\cdots,\pm n\right\}\right|\leqslant\left|\left\{\left.\displaystyle\sum_{i=1}^{k}x_ia_i\,\right|x_i\in\{-1,0,1\},\ i=1,2,\cdots,k\right\}\right|\leqslant 3^k,\]即$n \leqslant \dfrac{3^k-1}{2}$.

设$\dfrac{3^{m-1}-1}{2}<n \leqslant\dfrac{3^m-1}{2}$,其中$m\in \mathbb{N}^{*}$,则$k \geqslant m$.

当$k=m$时,取\[a_1=1,a_2=3,\cdots,a_m=3^{m-1},\]由数的三进制表示可知,对任意$p\in \left\{0,1,2,\cdots,3^m-1\right\}$,都有$p=\displaystyle\sum_{i=1}^{m}y_i3^{i-1}$,其中$y_i\in\{0,1,2\}$,因此\[p-\dfrac{3^{m-1}-1}{2}=\displaystyle\sum_{i=1}^{m}y_i3^{i-1}-\displaystyle\sum_{i=1}^{m}3^{i-1}
=\displaystyle\sum_{i=1}^{m}\left(y_i-1\right)3^{i-1}.\]令$x_i=y_i-1$,则$x_i\in\{-1,0,1\}$,$i=1,2,\cdots,m$.故对任意整数$$l\in\left[-\dfrac{3^m-1}{2},\dfrac{3^m-1}{2}\right],$$都有\[l=\displaystyle\sum_{i=1}^{m}x_i3^{i-1},\]其中$x_i\in\{-1,0,1\}$,$i=1,2,\cdots,m$.

由于$n \leqslant \dfrac{3^m-1}{2}$,因此,对一切正整数$l\in[-n,n]$,也有上述表示.

综上所述,$k$的最小值$f(n)=m$,其中$\dfrac{3^{m-1}-1}{2}<n \leqslant\dfrac{3^m-1}{2}$,$m\in \mathbb{N}^{*}$.

 可以进一步证明,当且仅当$n=\dfrac{3^m-1}{2}$,$m\in \mathbb{N}^{*}$时,上述$f(n)$块砝码的组成方式是唯一确定的.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表评论