Решение системы Р-35 ВКонтакте Методом Отображений

Would you like this post to be rewritten in English

Just let me know.



  

Построим базовую диаграмму и определим функцию , задающую отображение. При построение базовой диаграммы мы игнорируем (┐x3~y1), Так как у1 однозначно определяется кортежем {x}
                                              f(00) = f(00) + f(10)
      Значения в столбце (n)    f(01) = f(00) + f(10)  Значения в столбце (n-1)
                                              f(11) = f(11)
  

 

 
   Нетрудно видеть , что метод отображений генерирует явным образом
   ряд Фибоначчи 5,8,11,21,34,55.Если обозначить
   R(8) -  число цепочек оканчивающихся на 01, то R(8)=21
   Z(8) -  число цепочек оканчивающихся на 00 или 10, то  Z(8)=34
   Метод отображений также доказывает , что R(n),Z(n),K(n) являются
   последовательностями Фибоначчи. Для n=8 получаем

                 K(8)=R(8) + Z(8) = 55

   ( ¬y7 v y8 ) =1 имеет 3 решения

   Ответ : -  55*3=165

**********************************************************************************
 Доказательство Е. Н. Евич  http://kpolyakov.spb.ru/download/ege23.doc
**********************************************************************************
   

  

 Пункт 5  по Е. Евич изложен не вполне корректно.

***********************************************************************
Следую it-n.ru/attachment.aspx?id=150390
с незначительной модификацией логики .
***********************************************************************
Пусть К(n) - количество цепочек длины "n",в которых
нет двух подряд идущих единиц.

K1(n) - кончаются на 1
К0(n) - кончаются на 0

Тогда

K1(n+1)= K0(n)
K0(n+1)= K1(n) + K0(n) = K(n)
K(n+1) = K1(n+1) + K0(n+1) = K0(n) + K0(n+1) = K0(n) + K(n)

В силу того , что
K0(n)=K(n-1)
Получаем
K(n+1) = K(n) + K(n-1)
чтд.

   

Once again bitmasks versus Mapping Metod on Classic EGE "Problem"

Originally suggested in 2011

 

    Notice that

   ( x1^x2 v ¬x1^x2) v (¬x3^x4 v x3^¬x4) = 1
   ( x3^x4 v ¬x3^x4) v (¬x5^x6 v x5^¬x6) = 1
   . . . . . .
   ( x7^x8 v ¬x7^x8 ) v (¬x9^x10) v x9^¬x10) = 1

   might be converted via substitution

    z1 = (x1~x2)
    z2 = (x3~x4)
   . . . . . .
   z4 = (x7~x8)
   z5 = (x9~x10)

   into next one

   z1 v ¬z2  =1
   z2 v  ¬z3 =1
   z3 v ¬z4  =1
   z4 v ¬z5  =1


  The last one is equvalent to

 z2 => z1 =1
 z3 => z2 =1
 z4 => z3 =1
 z5 => z4 =1


z5  z4  z3 z2  z1
-------------------------
1    1    1   1   1
0    1    1   1   1
0    0    1   1   1
0    0    0   1   1
0    0    0   0   1
0    0    0   0   0


Answer would be 6*2^5= 192

*****************************
Mapping method
*****************************

(x1~x2) v ¬(x3~x4)  = 1
(x3~x4) v ¬(x5~x6)  = 1
(x5~x6) v ¬(x7~x8)  = 1
(x7~x8) v ¬(x9~x10)= 1

  

Классика Жанра Метод Отображений versus Иформатик БУ битовые маски - простота и доступность для ребят без ученых степеней

 Сколько существует различных наборов значений логических переменных
x1, x2, ... x8, y1, y2, ... y8, которые удовлетворяют всем перечисленным ниже условиям?


(x1 ∨ x2) ∧ (x1 ∧ x2 → x3) ∧ (¬x1 ∨ y1) = 1
(x2 ∨ x3) ∧ (x2 ∧ x3 → x4) ∧ (¬x2 ∨ y2) = 1
...
(x6 ∨ x7) ∧ (x6 ∧ x7 → x8) ∧ (¬x6 ∨ y6) = 1
(x7 ∨ x8) ∧ (¬x7 ∨ y7) = 1
¬x8 ∨ y8 = 1



   Видео от Информатика БУ ( понятно для самого ленивого и никогда
   не слышавшего о системах логических уравнений )

  https://www.youtube.com/watch?v=MDL5Mym5Aac

  Ортодоксальный подход  Е. Мирончик - Метод отображений
  Источник сайт К. Полякова.
  Великолепно, слов нет. Но есть вопрос для какой категории лиц ?

  

 

  

Решение системы логических уравнений x1=>x2=> ...=>x6=1 && y1=>y2=> ...=>y6 && x1=>y1 Методом Отображений

Исходная система  :-

x1 => x2 => x3 => x4 => x5 => x6 =1
y1 => y2 => y3 => y4 => y5 => y6 =1
x1 => y1 =1


Далее мы следуем методу изначально изложенному в работе
http://www.loiro.ru/files/news/news_943_etodotobrajeniya-mea-2013-10.pdf

Построим базовую диаграмму и определим функцию  F( ) для генерации
таблицы Методом Отображений по Е. Мирончик



   Определим число решений уравнения
   x1 => x2 => x2 => x3 => x4 => x5 => x6 =1  при x1=1
  

   Определим число решений уравнения
   y1 => y2 => y3 => y4 => y5 => y6 =1  при y1=0

   Подсчитаем число кортежей {x},{y} не удовлетворяющих третьему
   уравнению ситемы, чтобы затем вычесть его из 43^2
  
   
   Для этого определим число решений уравнений
   x1=>x2=>x3=>...=>x6=1
   y1=>y2=>y3=>...=>y6=1
   используя технику Метода Отображений
  
  
   Таким образом, получаем ответ :-  Count = 43^2 - 21*22 = 1387

   

Solution of one system of equations in boolean variables having style like x1 => x2 => ... =>x6=1 && y1 => y2 => ... =>y6 =1 && x1 => y1 via Mapping method

Original system looks like :-

x1 => x2 => x3 => x4 => x5 => x6 =1
y1 => y2 => y3 => y4 => y5 => y6 =1
x1 => y1 =1


Down here we follow approach originally developed in
http://www.loiro.ru/files/news/news_943_etodotobrajeniya-mea-2013-10.pdf


Build basic diagram and define function F( ) to apply Mapping method
suggested  by E. Mironchick

   Now calculate number of solutions of equation
   x1 => x2 => x2 => x3 => x4 => x5 => x6 =1  starting with  x1=1
     

    Calculate  number of solutions of equation
    y1 => y2 => y3 => y4 => y5 => y6 =1  starting with y1=0

   So, we intent to calculate number  of {x},{y} corteges breaking
   third equation and afterwards deduct amount been obtained  from 43^2

     

  Keeping in mind

 

   
 Thus final answer is : -   Count = 43^2 - 21*22 = 1387
 

Решение 23 Регион 61 ЕГЭ 2017 методом отображений

Изначальная постановка

(x1 V ┐x2) ^ (y1 V ┐y2) ^ (┐x1 V y1) = 1
(x2 V ┐x3) ^ (y2 V ┐y3) ^ (┐x2 V y2) = 1
(x3 V ┐x4) ^ (y3 V ┐y4) ^ (┐x3 V y3) = 1
(x4 V ┐x5) ^ (y4 V ┐y5) ^ (┐x4 V y4) = 1
(x5 V ┐x6) ^ (y5 V ┐y6) ^ (┐x5 V y5) = 1
(┐x6 V y6) = 1

Следую  Alexey Bogdanov
 

 

   Диаграмма в верхнем правом углу неверна. Рассчитанная матрица правильна , но не соответсвует диаграмме. Например , из диаграммы

следует

f(00) = f(01) + f(10) + f(11)

На пересечении столбца x3y3 и строки 00 должно быть 4.

Строим правильную диаграмму и функцию f( )

  
 

 

  Строим корректную функцию f( )  :-

  f(00) = f(00) + f(01) + f(11)

  f(01) = f(01) + f(11)

  f(10) = f(11)

  f(11) = f(11)

  

Генерируем таблицу :-

 

   

           

Solution task 23 region 61 EGE 2017 via bitmasks

***************************************
Original system looks like 
***************************************
(x1 V ┐x2) ^ (y1 V ┐y2) ^ (┐x1 V y1) = 1
(x2 V ┐x3) ^ (y2 V ┐y3) ^ (┐x2 V y2) = 1
(x3 V ┐x4) ^ (y3 V ┐y4) ^ (┐x3 V y3) = 1
(x4 V ┐x5) ^ (y4 V ┐y5) ^ (┐x4 V y4) = 1
(x5 V ┐x6) ^ (y5 V ┐y6) ^ (┐x5 V y5) = 1
(┐x6 V y6) = 1

Split original system into 3 equvalent first one :-

******************
System 1
******************

x2 => x1 = 1
x3 => x2 = 1
x4 => x3 = 1
x5 => x4 = 1
x6 => x5 = 1

*****************
System 2
*****************

y2 => y1 = 1
y3 => y2 = 1
y4 => y3 = 1
y5 => y4 = 1
y6 => y5 = 1

***********************************************************************
System 3 ( toi be taken in account when concantenating X and Y)
***********************************************************************
x1 => y1 = 1
x2 => y2 = 1
x3 => y3 = 1
x4 => y4 = 1
x5 => y5 = 1
x6 => y6 = 1

Build bitmasks for {x} and {y}

x6 x5 x4 x3 x2 x1
------------------
1  1  1  1  1  1 
0  1  1  1  1  1 
0  0  1  1  1  1
0  0  0  1  1  1 ==>
0  0  0  0  1  1 
0  0  0  0  0  1 
0  0  0  0  0  0

y6 y5 y4 y3 y2 y1
------------------
1  1  1  1  1  1 <==
0  1  1  1  1  1 <==
0  0  1  1  1  1 <==
0  0  0  1  1  1 <==
0  0  0  0  1  1  => 5-th row is not allowed for concateneting with 4-th row fom X
0  0  0  0  0  1        due to x3=1 and y3=0 . Hence x3 => y3 =0 ( 1 => 0)
0  0  0  0  0  0 

We would name them further matrix X and matrix Y 

************************
Now start concatenate
************************
First row from X with first row from Y
due to x6 => y6 =0

Second row from X with first and second rows from Y
Analyze attempt to pick up third row from Y
Then we'll get x5 => y5 = 0

Third row from X with rows 1,2,3 from Y
Analyze attempt to pick up fourth  row from Y
Then we'll get x4 => y4 =0

. . . . . . . . . . . . . . . . . . . 

Row number k from X may be concatenated with first k rows from Y
Analyze row (k+1) from Y  it has 0 on place number (k),
and x(k) = 1 in row number k from X
Then we'll get (x(k) => y(k)) = 0 where y(k)=0  belongs row (k+1) from Y

Thus final count = 1 +2 +3 + 4 + 5 + 6 +7 =(7*8)/2 = 28

General approach to task 17 in EGE Mathematics

58564(q^4-1)/(q-1)=Sq^4
106964(q^2-1)/(q-1)=Sq^2, where q=1+r/100
keep in mind that (q^4-1)= (q^2-1)(q^2+1)
In second equation (q^2-1)= (q-1)(q+1)
Proceed as follows

58564(q^2-1)(q^2+1)/(q^2-1)=Sq^4/(q+1)
106964 = Sq^2/(q+1)
Finally we get
58564(q^2+1) = 106964 q^2 => general approach to tasks of such a kind

q^2=58564:(106964-58564) => q=1.1  => r = 10%

VKontakte P-30 Задача 23 as of 01.06.17

   First notice that

   (x1^x2) v (x1 v x3)^(x1^y1)=0 is equivalent
   (x1^x2) v x1 v (x3^y1) this last one is equivalent
   x1 v ( x3^y1) due to absorption rule in Boolean algebra

   and so far converting each equation one by one.
  
  Converted system

  x1 v ( x3^y1)=0
  x2 v (x4^y2) =1
  x3 v (x5^y3) =0
  x4 v (x6^y4) =1
  x5 v (x7^y5) =0
  x6 v (x8^y6) =1

Now split system into two without any dependency between them

1.) In system 1 x1 =0,x3=0,x5=0  Number of solutions 2*2*3 = 12

x1 v ( x3^y1)=0
x3 v (x5^y3) =0
x5 v (x7^y5) =0

 
2) System 2 has 38 solutions.

 x2 v (x4^y2) =1
 x4 v (x6^y4) =1
 x6 v (x8^y6) =1

---------------------------
First column x4
---------------------------
K4 = 3  ; K(X) for value  "1",  X=2,4,6
Z4 = 2  ; Z(X) for value  "0",  X=2,4,6
------------------------------
Second column x6
------------------------------
K6=  2*K4 + Z4 =8
Z6 = 2*K4 =6
---------------------------------
Third column x8
---------------------------------
K8=  2*K6 + Z6 = 22
Z8 = 2*K6 = 16


Resulting number of {x2,x4,x6,x8},{y2,y4,y6} corteges is 38

Finally, we get 12*38 = 456