算法题——立方体的体对角线穿过多少个正方体？

大长方形的对角线,会穿过多少个小正方形

问：有多少个正整数n（n＜2015）满足条件：1/3＋1/n可以化简为分母小于n的分数？

1/3＋1/n=（3＋n）/3n
要使1/3＋1/n可以化bai简为分母du小于n的分数，则分子（zhi3＋n）与分母3n有大于或等于4的公约dao数，设此公约数为d（d>=4）
1）若d中没有因数3，则d是n的因数。设n=da（a是大于1的正整数），则
分子3＋n=3＋da=（3/d＋a)*d,由于a是整数，则3/d是整数，即d=1，2，这样的d不满足题设。
2）d中必有因数3，则d=3k（因为d>=4,则k是大于1的正整数）。由于分母是3n，则k是n的因数，设n=tk（t是正整数）。
分子3＋n=3＋tk=（3＋tk）/3k*3k，由于（3＋tk）/3k是整数，则设（3＋tk）/3k=m（m是正整数），则（3m-t）k=3
得k=3且3m-t=1，则t=3m-1
n=tk=（3m-1）*3=9m-3（m是正整数）
由于n<2015，得9m-3<2015,解得m<2018/9,m最大值取224.
即224个这样的正整数n。

(排序不等式)设有两个有序数组: $a_1leqslant a_2leqslantcdotsleqslant a_n$及$b_1leqslant b_2leqslant cdotsleqslant b_n$.求证:
egin{align*}
a_1b_1+a_2b_2+cdots+a_nb_n\, ext{(顺序和)}\
geqslant a_1b_{j_1}+a_2b_{j_2}+cdots+a_nb_{j_n}\, ext{(乱序和)}\
geqslant a_1b_n+a_2b_{n-1}+cdots+a_nb_1\, ext{(逆序和)},
end{align*}
其中$j_1,j_2,cdots,j_n$是$1,2,cdots,n$的任意一个排列.

令$S_i=b_1+b_2+cdots+b_i$, $S'_i=b_{j_1}+b_{j_2}+cdots+b_{j_i}\,(i=1,2,cdots,n)$.

由题设可知$S_ileqslant S'_i\,(i=1,2,cdots,n-1)$且$S_n=S'_n$.

又因为$a_i-a_{i+1}leqslant 0$,故$S_i(a_i-a_{i+1})geqslant S'_i(a_i-a_{i+1})$.

所以
egin{align*}
sum_{i=1}^{n}a_ib_i &=sum_{i=1}^{n-1}S_i(a_i-a_{i+1})
+a_nS_n\
&geqslantsum_{i=1}^{n-1}S'_i(a_i-a_{i+1})
+a_nS'_n=sum_{i=1}^{n}a_ib_{j_i}.
end{align*}
此即左端不等式.类似可证得右端不等式.

extbf{证法二.}令$S=a_1b_{j_1}+a_2b_{j_2}+cdots +a_nb_{j_n}$.

若$j_n eq n$,且此时$b_n$所在的项是$a_{j_m}b_n$,则由$(b_n-b_{j_m})(a_n-a_{j_m})>0$得
$$a_nb_n+a_{j_m}b_{j_n}geqslant a_{j_m}b_n+a_nb_{j_n},$$
这就是说, $j_n eq n$时,调换$S$中$b_n$与$b_{j_n}$的位置,其余都不动,则得到$a_nb_n$项，并使S变为S，，且S，>S.
用类似的方法，可以再得到a-16-1项，并使S，变为S2，且S2>S..
这个过程可

以继续进行下去，至多经过n-1次调换，即可得到a1b，+a2b +..+a，b，，故有a1b，+
a2b2+..+4b.>S.
类似地可以证明S>a1b，+a2b.1+..+ab.
显然，当a1=a2=.a，或b，=b2=.b，时，两个等号同时成立.

反过来，若la，，a2.，.）及1b，b，，b，中的数都不全相等，则必有a，+a，，bi+b..
于是ah +a，b，>alb.+a.b，.且a2b + +a1b-1 > a2b-1 + +ab，从而有alb +a2bs +
.+ ab，> a1b.+ a2bt..+ab.
故这两个等号中至少有一个不成立.