Диагональ прямоугольного параллелепипеда

[Ktina]

Прямоугольный параллелепипед $150\times 324\times 375$ склеен из единичных кубиков.
Сколько кубиков "пронзает" диагональ такого параллелепипеда?

[hippie]

Ответ: 768.
($150+324+375-6-3-75+3.$)

[Dave]

Решение в общем случае. Пусть в $\mathbb R^n$ прямоугольный параллелепипед $a_1 \times a_2 \times \dots \times a_n$ склеен из единичных гиперкубиков ($a_i \in \mathbb N$, $i=\overline {1,n}$). Если выбрать начало координат в одной из вершин параллелепипеда, а оси направить по его рёбрам в сторону диагонально противоположной вершины, то параметрическое уравнение диагонали будет иметь вид $x_i=a_it$, $i=\overline {1,n}$, $t \in [0,1]$. "Пронзание" диагональю параллелепипеда гиперкуба $\prod_{i=1}^n {[x_i,x_i+1]}$ для какого-либо набора целых чисел $x_i$, $0 \leqslant x_i < a_i$, т.е. наличие пересечения этой диагонали со внутренностью гиперкуба, равносильно существованию такого числа $t \in [0,1]$, что $x_i<a_it<x_i+1$ для всех $i$, а это, в свою очередь, равносильно

$$\max_{i=1}^n {\frac {x_i} {a_i}} < \min_{i=1}^n {\frac {x_i+1} {a_i}} \qquad \eqho(1)$$

Пусть $X$ - множество всех допустимых наборов $(x_i)_{i=1}^n$ (т.е. тех, что $x_i \in \mathbb Z, 0 \leqslant x_i < a_i$). Пусть также $\Lambda$ - конечное множество значений, которые принимает левая часть $(1)$ при всех допустимых наборах и пусть для любого непустого множества $I \subseteq \{1,2,\dots,n\}$ и $\lambda \in \Lambda$, $X(I,\lambda)$ - множество наборов из $X$, для которых $\frac {x_i} {a_i}=\lambda$ при всех $i \in I$ и $\frac {x_i} {a_i} \leqslant \lambda <\frac {x_i+1} {a_i}$ при остальных $i$. Тогда по формуле включений-исключений, при каждом фиксированном $\lambda \in \Lambda$, количество допустимых наборов, для которых выполняется $(1)$ и при этом левая часть $(1)$ равна $\lambda$, подсчитывается по формуле

$$S(\lambda)=\sum_{I \subseteq \{1,2,\dots,n\}, I \neq \varnothing} {(-1)^{|I|-1}|X(I,\lambda)|}$$

В задаче требуется найти число

$$S=\sum_{\lambda \in \Lambda} {S(\lambda)}=\sum_{I \subseteq \{1,2,\dots,n\}, I \neq \varnothing} {(-1)^{|I|-1} {\sum_{\lambda \in \Lambda} {|X(I,\lambda)|}}} \eqno(2)$$

Зафиксируем теперь какое-либо множество индексов $I$ и пусть $d=d_I=\gcd_{i \in I} {a_i}$- наибольший общий делитель соответствующих ему чисел $a_i$. Если $a_i=db_i$, то числа $b_i$ имеют НОД, равный $1$, и равенство $\frac {x_i} {a_i}=\lambda$ при всех $i \in I$ равносильно

$$\frac {x_i} {b_i}=d\lambda \eqno(3)$$

Если число $d\lambda$ нецелое, то $(3)$ не может выполняться при всех $i \in I$. При $|I|=1$ это очевидно ($b_i=1$, $I=\{i\}$), а при $|I|>1$ это получается из рассмотрения равенства $x_{i_1}b_{i_k}=x_{i_k}b_{i_1}$, где $b_{i_k}$ взаимно просто с каким-либо простым делителем $b_{i_1}$, на предмет делимости на максимальную степень этого простого числа, входящего в $b_{i_1}$ - $x_{i_1}$ должно делиться на эту степень; объединяя все эти рассуждения, получим, что $x_{i_1}$ делится на $b_{i_1}$. С другой стороны, если $h=d\lambda$ - целое, $\lambda \in \Lambda \subseteq [0,1)$, то $X(I,\lambda)$ будет состоять из единственного набора, в котором $x_i=hb_i=\lambda a_i$ при $i \in I$ и $x_i= [ \lambda a_i ]$ при $i \notin I$. Это значит, что внутренняя сумма в правой части $(2)$ в точности равна $d_I$, ибо только при $\lambda=\frac h d$, $h=\overline {0,d-1}$ число $d\lambda$ - целое. Итак, верна следующая формула:

$$S(a_1,a_1,\dots,a_n)=\sum_{I \subseteq \{1,2,\dots,n\}, I \neq \varnothing} {(-1)^{|I|-1} \gcd_{i \in I} {a_i}}$$

В частности, если числа $a_i$ попарно взаимно-просты, то $S(a_1,a_1,\dots,a_n)=a_1+a_2+\dots+a_n+1-n$.