2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 На каком числе наборов логич. ф-ция принимает значение 1
Сообщение19.02.2007, 13:01 


25/12/06
63
На каком числе наборов ф-ция принимает значение 1
$$f(x_1 ,...,x_n ) = x_1 x_2  \oplus x_2 x_3  \oplus ... \oplus x_{n - 1} x_n $$
Понятно что, если нечетное число произведений равны 1 , то и функция равна 1. Произведения равны 1 когда оба сомножителя 1, но при этом они влияют на соседние и т.д. Наверное такое рассуждение не совсем красивое, поэтому трудно как-то подсчитать, подскажите пожалуйста покрасивее.

 Профиль  
                  
 
 
Сообщение19.02.2007, 13:31 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Используйте соображение, что в ряду $x_1,\ldots,x_n$ каждая пара соседних единиц дает ровно одну единицу в рассматриваемую сумму.

Ответ можно выразить через общее количество единиц в наборе переменных и количество блоков последовательных единиц.

 Профиль  
                  
 
 
Сообщение19.02.2007, 14:24 


25/12/06
63
Никак не могу учесть правильно наборы вида ...111..., которые дают $1 \oplus 1 = 0$

 Профиль  
                  
 
 
Сообщение19.02.2007, 14:26 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Сколько единиц в сумму даст блок длины $k$? Блоком называем последовательность переменных, индексы которых идут подряд, которые все равны 1 и к который нельзя расширить ни влево, ни вправо.

 Профиль  
                  
 
 
Сообщение19.02.2007, 14:33 


25/12/06
63
блок длины $k$ даст в сумму $k - 1$ единиц, а дальше только остается поиграть четностью? так да?

 Профиль  
                  
 
 
Сообщение19.02.2007, 14:51 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Городецкий Павел писал(а):
блок длины $k$ даст в сумму $k - 1$ единиц


Верно. В частности, блок длины 1 не даст ни одной единицы в сумму.

А теперь пусть нам известно, что в ряду переменных имеется $m$ блоков единиц и их совокупная длина равна $k$. Как выразить число единиц в искомой сумме через эти параметры?

 Профиль  
                  
 
 
Сообщение19.02.2007, 15:24 


25/12/06
63
Вот тут уже хуже - мне кажется что эта задача равносильна размещению $k$ непомеченных частиц по $ m $ помеченным ящикам (разбиралось на семинаре) т.е. $$C_{k + m - 1}^k $$

 Профиль  
                  
 
 
Сообщение19.02.2007, 15:29 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Нет, все проще гораздо. Смотрите: для каждого блока мы берем число единиц в нем и вычитаем 1.

Добавлено спустя 1 минуту 4 секунды:

Например, пусть есть два блока ($m=2$) и их длины равны $k_1$ и $k_2$. Сколько тогда единиц будет в сумме?

 Профиль  
                  
 
 
Сообщение19.02.2007, 15:36 


25/12/06
63
Если известна длина каждого блока, то число единиц $$\sum\limits_{i = 1}^m {(k_i  - 1)$$
где $${\sum\limits_{i = 1}^m {k_i  = k} }$$

 Профиль  
                  
 
 
Сообщение19.02.2007, 15:49 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Правильно. И раскрывая скобки получаем, что количество единиц в сумме равно просто $k-m$. Функция равна 1 тогда и только тогда, когда это число нечетное.

Может быть, существуют и другие способы охарактеризовать все наборы переменных, на которых данная функция равна 1. Но, по-моему, этот наиболее простой.

Добавлено спустя 8 минут 21 секунду:

Не очень внимательно посмотрел, что речь идет о подсчете всех наборов. Это надо подумать...

 Профиль  
                  
 
 
Сообщение19.02.2007, 15:54 


25/12/06
63
Супер :)
То есть в итоге необходимо найти количество наборов у которых $k-m$ нечетно, где m - количество блоков, а k - совокупная длина.
Только я что-то опять подтормаживаю как это сделать

 Профиль  
                  
 
 
Сообщение19.02.2007, 16:09 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Придумалось следующее соображение, основанное на рекуррентных соотношениях.

Обозначим через $f_1(n,0)$ число всех наборов переменных длины $n$, таких что $x_n=0$ и искомая функция равна 1. Аналогично $f_1(n,1)$ - все такие наборы, оканчивающиеся на 1. Сумма $f_1(n)=f_1(n,0)+f_1(n,1)$ - то, что требуется найти.

Используем тот факт (вытекающий из полученного результата), что если набор оканчивается на 0, то при приписывании к нему еще одной переменной значение рассматриваемой функции не меняется. А если набор оканчивается на 1, то от приписывания нуля значение функции не меняется, а от приписывания единицы - меняется на противоположное.

Тогда можно записать следующие рекуррентные соотношения:
$$f_1(n,0)=f_1(n-1,0)+f_1(n-1,1)=f_1(n-1)$$
$$f_1(n,1)=f_1(n-1,0)+f_0(n-1,1)$$
Складываем и учитываем, что сумма $f_1(n-1,1)+f_0(n-1,1)$ равна числу всех наборов длины $n-1$, оканчивающихся на 1, т.е. $2^{n-2}$.
$$f_1(n)=f_1(n,0)+f_1(n,1)=2f_1(n-1,0)+2^{n-2}=2f_1(n-2)+2^{n-2}$$

Получилось рекурретное соотношение. Правда, не соображу, как его решать...

Добавлено спустя 3 минуты 4 секунды:

Впрочем, нет, все ясно: если теперь подставить вместо $f_1(n-2)$ такое же рекуррентное соотношение и так далее, то видно, что получается сумма геометрической прогрессии. В общем, далее уже можно считать. Нужно только отдельно рассмотреть случаи четных и нечетных $n$.

 Профиль  
                  
 
 
Сообщение19.02.2007, 16:28 


25/12/06
63
PAV
Я понял - я просто теперь думаю как это решение представить без рекурентности - все-таки 1 курс вечернего - мы еще пока не проходили
Я думаю тогда так написать (извините за плагиат):

Обозначим через $N1_{1,n}$ число всех наборов переменных длины $n$, таких что $x_n=0$ и искомая функция равна 1. Аналогично $N2_{0,n}$ - все такие наборы, оканчивающиеся на 1. Сумма $N_n=N1_{1,n}+N2_{0,n}$ - то, что требуется найти.

Используем тот факт (вытекающий из полученного результата), что если набор оканчивается на 0, то при приписывании к нему еще одной переменной значение рассматриваемой функции не меняется. А если набор оканчивается на 1, то от приписывания нуля значение функции не меняется, а от приписывания единицы - меняется на противоположное.

и так далее по тексту

 Профиль  
                  
 
 
Сообщение19.02.2007, 16:40 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Да в общем-то это одно и то же, Вы просто слово "рекуррентность" можете не произносить... Пишите как хотите, главное, чтобы было правильно.

А вообще по-моему не надо бояться показать какие-то знания, которым Вас не учили.

 Профиль  
                  
 
 
Сообщение19.02.2007, 23:40 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Не до конца вникал в рассуждения, но если надо решить рекуррентность
$$f_1(n)=2f_1(n-2)+2^{n-2},$$
то можно просто поделить это соотношение на $2^{\frac n2}$. Если обозначить $g(n)=f_1(n)2^{-\frac n2}$, то получим
$$g(n)=g(n-2)+2^{\frac n2-2}.$$

Или переписать в виде
$$f_1(n)-2^{n-1}=2(f_1(n-2)-2^{n-3}).$$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group