Шешімі: Подсчёт наборов логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_{10}, y_1, y_2, \ldots, y_5$, которые удовлетворяют всем приведённым ниже условиям?
$$(x_i \land y_j \to x_i \land y_{j+1}) \land (x_i \land y_j \to x_{i+1} \land y_j)=1$$
для всех натуральных $i$ и $j$, таких что $i<10$ и $j<5$.
Шешімін қадамдап көрсету
5 қадамЕсли $x_i \land y_j=1$, то обе импликации должны быть истинными, поэтому $x_{i+1}=1$ и $y_{j+1}=1$.
Рассмотрим случай, когда среди $x_1,\ldots,x_9$ нет единиц. Тогда первые девять значений $x$ равны нулю, а $x_{10}$ выбирается двумя способами. Последовательность $y$ произвольна: $2\cdot 2^5=64$ наборов.
Если среди $x_1,\ldots,x_9$ есть единица, а среди $y_1,\ldots,y_4$ единиц нет, то последовательность $y$ имеет 2 варианта. Для $x$ возможны $2^{10}-2=1022$ вариантов. Получаем $1022\cdot2=2044$.
Если единицы есть и среди $x_1,\ldots,x_9$, и среди $y_1,\ldots,y_4$, то после первой единицы в каждой последовательности должны идти только единицы. Для $x$ таких последовательностей $9$, для $y$ — $4$. Получаем $9\cdot4=36$.
Складываем непересекающиеся случаи.
$$64+2044+36=2144$$Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывают только одну из двух импликаций.
Забывают отдельно рассмотреть случаи, когда в одной из последовательностей нет единиц среди первых элементов.
Считают условие как дизъюнкцию требований вместо одновременного выполнения обеих импликаций.