tag:blogger.com,1999:blog-8870493191508591473.post4731729074853570354..comments2023-06-20T15:29:20.647+03:00Comments on Крылья, ноги... Хвост!: Задачка: Vladimir Dolzhenkohttp://www.blogger.com/profile/09353866985268525403noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-8870493191508591473.post-88291959414141037452012-09-11T02:05:04.145+04:002012-09-11T02:05:04.145+04:00Идея примерно такая же.
I Докажем: для любого x>...Идея примерно такая же.<br />I Докажем: для любого x>=2 cуществует посл-ть операторов {R,...L,..} такая, что второй элемент столбца R*...*(0,1)T равен x. При чем количество элементов последовательности соответствует числу знаков в двоичной записи числа x-1, где операторы L стоят на месте нулей , а R на месте единиц. Так, 21-1=10101 -1=10100. Значит число 21 - это второй элемент столбца RxLxRxLxLx(0 1)T. Доказательство по индукции. <br />1)2:2-1=1 - оператор R<br /> 3:3-1=10 - оператор RL , <br /> 4:4-1=11 - RR. Т.о, для чисел x , для которых x-1 в двоичной записи имеет менее 3-х знаков доказано. <br />2)Предположим, что утверждение доказано для всех чисел, в двоичной записи которых n знаков.<br />A - произведение операторов длины n <br /> A*(0,1)T ->x<br />Тогда <br /> A*R = [(a11 b12)(-x+1 x)] *[(1 0)(-1 2)]=[(c11 c12)(-2*x+1 2*x)] (1)<br /> A*R*(0,1)T -> 2*x - эквивалентно дописыванию 1 справа к двоичной записи x-1<br /> A*L= [(a11 b12)(-x+1 x)]*[(2 -1)(0 1)]=[(d11 d12)(-2*x+2 2*x-1)] (2)<br /> A*L*(0,1)T -> 2*x-1 - дописали 0 к двоичной записи x-1 <br /> Т.о., можем получить любую двоичную последовательность длины n+1.<br /> (То, что последняя строка матрицы A имеет вид (-x+1 x) можно показать по индукции, но это видно также из (1) и (2): умножение на R и L не меняет этого соотношения)<br />II Аналогично для x<0. Произведение операторов начинается с L. Тогда для любого числа x<0 существует последовательность операторов {L,...R,..}такая что первый элемент столбца Rx...(0,1)T равен x. Количество элементов последовательности соответствует числу знаков в двоичной записи числа abs(x), где операторы R стоят на месте нулей , а L на месте единиц.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8870493191508591473.post-13741175656234036002012-09-05T16:46:04.342+04:002012-09-05T16:46:04.342+04:00Любая последовательность операторов длины в точнос...<br />Любая последовательность операторов длины в точности n позволяет<br />получить все числа [-2^n+1 2^n]<br /><br />Индукция по n<br /><br />Будем доказывать более сильное утв.<br />А именно все пары (x, y) имеют след структуру<br />если x > 0 то y = x - 2^k соотв. x [0 .. 2^n] (a)<br /><br />База индукции:<br />n=1 (0, 1) верно<br /><br />Шаг индукции:<br />Пусть для n <= k утв. верно<br />Рассмотрим пары для шага k+1<br />Для каждого числа x > 0 x <= 2^(k+1) необходимо показать, что есть<br />пара полученная не пред шаге, и применение одного из двух операторов<br />позволит получить пару с компонентом равным x (те сделав k+1 шаг) и<br />условием на связь x и y (a)<br /><br />случай а)<br />Если x > 0 and x <= 2^k (те x мало) то, по предположению индукции есть пара с соотв. x<br />и можно применить один из операторов сохраняющий соотв. компонент.<br />Остается проверить, связь (a)<br /><br />Без огр. общности x - первый компонент (иначе аналогично с заменой операторов)<br />R(x,y) = (x,2y-x)<br />x1 = x<br />y1 = 2y-x<br /><br />y1 = 2y-x = 2(x-2^k) - x = 2x - 2^(k+1) - x = x - 2^(k+1)<br />утв. выполнено<br /><br />случай б)<br />x > 2^k но тогда y = x - 2^k т.е. в данном случае y подпадает под предположение индукции.<br />и проводя абсолютно аналогичные расссуждения получим искомое.<br /><br />Прошу прощения, слегка сумбурно выразился, но смысл вроде в этом есть.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8870493191508591473.post-17478675688785202582012-09-05T15:47:44.969+04:002012-09-05T15:47:44.969+04:00@Анонимный
нет, всё конечно хорошо, только вот .....@Анонимный<br /><br />нет, всё конечно хорошо, только вот ... почему именно так<br /><br />и как бы идея, что c помощью любой последовательности операторов длины в точности n можно получить все числа используя эти операторы далеко <b>не очевидна</b>Vladimir Dolzhenkohttps://www.blogger.com/profile/09353866985268525403noreply@blogger.comtag:blogger.com,1999:blog-8870493191508591473.post-39906502465177510962012-09-05T15:05:07.527+04:002012-09-05T15:05:07.527+04:00ad-hoc-v2a-a-little-bit-smaller<a href="https://raw.github.com/gist/3634231/4ed749ede35f93530a585d3da9f9139008295106/gistfile1.clj" title="" rel="nofollow">ad-hoc-v2a-a-little-bit-smaller</a>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8870493191508591473.post-90610931842898107372012-09-05T14:35:09.822+04:002012-09-05T14:35:09.822+04:00ad-hoc-solution-v2
Идея: c помощью любой последова...<a href="https://raw.github.com/gist/3634231/b5d3a73dddf53bec0216d86b4a796d594ce17542/gistfile1.clj" title="" rel="nofollow">ad-hoc-solution-v2</a><br />Идея: c помощью любой последовательности операторов длины в точности n можно получить все числа [-2^n+1 2^n].Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8870493191508591473.post-75015652682044392252012-09-05T13:57:53.503+04:002012-09-05T13:57:53.503+04:00@Анонимный
да и с таким заходом вообще-то не стыд...@Анонимный<br /><br />да и с таким заходом вообще-то не стыдно и подписаться)Vladimir Dolzhenkohttps://www.blogger.com/profile/09353866985268525403noreply@blogger.comtag:blogger.com,1999:blog-8870493191508591473.post-51979418699404500672012-09-05T13:57:29.560+04:002012-09-05T13:57:29.560+04:00@Анонимный
честно сказать давно уже не брал шашку...@Анонимный<br /><br />честно сказать давно уже не брал шашку в руки с clojure, выглядит красиво, но что-то не пойму до конца ход мысли<br /><br />ps. да и числа могут быть таки отрицательными.Vladimir Dolzhenkohttps://www.blogger.com/profile/09353866985268525403noreply@blogger.comtag:blogger.com,1999:blog-8870493191508591473.post-91175427029526714492012-09-05T13:49:53.268+04:002012-09-05T13:49:53.268+04:00ad-hoc-solution<a href="https://raw.github.com/gist/3634231/3ae7d02fdbd5d67ac46659b538ec245cc1ceb5cf/gistfile1.clj" title="" rel="nofollow">ad-hoc-solution</a>Anonymousnoreply@blogger.com