ферзи

[avva]

Забавная задачка от evan'а. Есть известная задача о том, как расставить 8 ферзей на шахматной доске так, чтобы они не атаковали друг друга. Решений очень много, и вручную в принципе не трудно какое-нибудь найти.

Но мы получим одно решение особым магическим путем. Шахматная доска 8x8, и ферзей 8, поэтому напишем формулу (2^8-1) / (8-1), это равно 255/7, и с точностью до 6 десятичных цифр это выходит 36.428571 . Если мы теперь будем ставить ферзей на горизонтали 3,6,4,2... по этому числу (двигаясь слева направо от первой вертикали к восьмой), то получится расстановка ферзей, которые не атакуют друг друга! Вопрос: как это работает?

(это решение использует одна компания в качестве лого, и объяснение с этой формулой есть у них на сайте по-английски)

Comments

[rakshas.livejournal.com]

При делении на 7 чисел от 1 до 6 получаются бесконечные периодические дроби из разных комбинаций цифр 4 2 8 5 7 1, подобрать целую часть (36 или 63) задача тривиальная.

Привязка к 8 в формуле 255/7 искусственная.

Если поделить 445 на 7, например, то тоже все получится.

[faceted-jacinth.livejournal.com]

а. Круто-круто.

[rakshas.livejournal.com]

Я же пишу: подбор. И даже привел пример, сам подобрал 445/7 = 63,(571428)

[avva.livejournal.com]

Ага, более или менее верно.

[faceted-jacinth.livejournal.com]

1023/9 = 113.(6) - фиг там
511/8 = 63.875 - фиг там
255/7 = 36.(428571) - о чудо!
127/6 = 21.1(6) - фиг там
63/5 = 12.6 - фиг там
31/4 = 7.75 - фиг там
15/3 = 5 - фиг там
7/2 = 3.5 - фиг там
3/1 = 3 - фиг там

Конечно, можно ещё менять основание системы счисления, но как-то это всё выглядит очень подозрительно, напоминая известный способ запомнить число 4268 - номер был одного паровоза в Печках, который стоял на шестнадцатом пути, и который нужно было увести на ремонт в депо Лысую-на-Лабе, однако у машиниста была слабая память на числа.

Вы уверены, что эту милую формулу можно как-то распространить на случай других досок? Иначе вопрос "как это работает" лишён всякого смысла, ИМХО.

а как нибудь доказывается это свойство деления на 7?

[aburachil.livejournal.com]

Какое именно свойство?

[aburachil.livejournal.com]

Я не вижу тут общего высказывания (кроме неких конкретных с цифрами, которые доказываются просто микрокалькулятором ;-). Сформулируйте теоремку, я Вам её докажу ;-)

[avva.livejournal.com]

Ну это не очень сложно. То, что период равен 6 или меньше, следует из того, что (1/7)*7 = 1. В периоде могут встречаться только такие цифры, которые при умножении на 7 дают число, оканчивающееся не на 0,1,2,3 (иначе еще бы одна семерка влезла при делении), это ровно отсекает 3,6,9,0. То, что встречаются все остальные, следует кажется из взаимной простоты 7 и 10, если просчитать по модулю 7 эти дела.

[aburachil.livejournal.com]

> (иначе еще бы одна семерка влезла при делении)
Я этого не понимаю.

> кажется из взаимной простоты 7 и 10
ИМХО этого недостаточно. Число 7 обладает таким свойством, что десятка имеет максимально возможную степень (6, разумеется) как элемент мультипликативной группы (Z/7Z)*. Например число 3 таким свойством не обладает (10=1 mod 3), а больше однозначных простых чисел, взаимно простых с основанием системы счисления и нету. Надо бы взять побольше основание, чтобы было примеров побольше. 16 вот например очень даже в тему. К тому же сегодня день как раз такой ;-)

[avva.livejournal.com]

Я этого не понимаю.

Ну вспомните, как в столбик делят. Взяли предыдущий остаток, например 3, добавили нолик, 30, и ищут частное от деления на семь. Но это не может быть 3, потому что 7*3=21 и последняя единица оставляет достаточно места для еще одной семерки втиснуться до 30. По той же причине не может быть 0,6,9.

> кажется из взаимной простоты 7 и 10 ИМХО этого недостаточно. Число 7 обладает таким свойством, что десятка имеет максимально возможную степень (6, разумеется) как элемент мультипликативной группы (Z/7Z)*.

О. Ну что-то в этом роде я подозревал, спасибо :)

Ну вспомните, как в столбик делят

[aburachil.livejournal.com]

А, дошло! Спасибо.

[avva.livejournal.com]

Нет, например 2/5 = 0.4000... , т.е. появляются нули.

[avva.livejournal.com]

Да, посчитайте 1/999.

[avva.livejournal.com]

Если делитель меньше основания системы, то 0 не может появиться и исчезнуть, да.

[aburachil.livejournal.com]

Вы упустили главное примечательное свойство волшебного числа 142857 [нам ведь удобнее оперировать целыми числами, а не бесконечными дробями, правда?] --- при умножении на 1,...,6 его цифры не только сохраняются сами по себе, но и сохраняют порядок следования (с точностью до циклической перестановки). Тут есть два вопроса. Первый --- почему число (10^(P-1)-1)/P для P равного семи обладает таким чудесным свойством? Второй --- почему все шесть цифр этого числа различны, и никакая из них не равна нулю и девяти. Заметьте, что второй вопрос это в точности то, о чём Вы спрашиваете (ну почти, Вы ещё спрашиваете, почему там нет тройки и шестёрки). Мне кажется, что первый вопрос существенно интереснее. Я нашла ответ на него, но, как говорил Пьер Ферма, ограничение на размер камента в ЖЖ не позволяет мне поместить сюда ответ. Например такой же феномен имеет место при P=19 или P=23, но не для 11 или 13. Ограничемся вторым вопросом, думая, что мы уже разобрались с первым. Итак, есть ровно шесть циклических перестановок цифр числа М (это 142857, но мы на секундочку забудем, что там именно эти цифры) и все они образуют числа М, 2M, ..., 6М. Предположим, что две цифры совпали, тогда имеем kM=X..... и k'M=X..... Следовательно (k-k')M это всего лишь пятизначное число, чего быть не может, так как М --- шестизначное. Ровно по этой причине невозможен и ноль. И поэтому же невозможна и девятка, ибо 7М=999999 и (7-k)М=7М-kM было бы не шестизначным. Осталось разобраться с тройкой и шестёркой. Это Вам домашнее задание. Подсказка --- наше число М обязано делиться на 9, а так как сумма всех цифр от 1 до 8 на 9 делится, получается, что сумма двух отсутстсвующих тоже делится на 9, так что есть не так уж и много вариантов.

[ivan-gandhi.livejournal.com]

How did you manage to discover Monica Anderson so fast? She just started!

[avva.livejournal.com]

Я не знаю вообще, кто это. Задачку дал Evan Martin evan в своем техническом дневнике evan_tech. Когда-то, еще до работы в Гугле, он писал много кода для ЖЖ, был одним из первых юзеров (потому что друг Брада), итд... я общался с ним, когда работал в ЖЖ, и с тех пор ценю и читаю.

есть у них на сайте по-английски

[aburachil.livejournal.com]

М-да, после такого "объяснения" мне лично кажется, что эта фирма --- шарлатанская.

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

[avva.livejournal.com]

Мне как раз это понравилось - подгонка хорошо скрыта, следы заметены.
Я даже не сразу увидел, что вообще говоря у периода 1/7 нет свойства диагонального ненападения, и пытался его доказать. Когда увидел, что на самом деле у 142857 его нет, понял, что это подгонка и речь идет о случайном подборе хорошей пермутации и еще двух цифр.

и пытался его доказать

[aburachil.livejournal.com]

Забавно, мы с Вами делаем совершенно одинаковые шаги, но разные выводы. Мой (пессимистический) вывод таков, что если они тут мозги бессовестно пудрят и пыль в глаза пускают, то будут так же и с клиентами поступать. Короче, в клиенты я к ним не пойду, а в акционеры --- пожалуй что да ;-)

[yurilax.livejournal.com]

может я чего не понимаю (а это совсем не редкость :), но у них на лого ряды доски пронумерованы сверху вниз, в то время как на канонических изображениях шахматных досок, они должны быть пронумерованы снизу вверх.

мелочь, конечно, но все же интересно - почему?


лого:



их решение:


36.428571

The eight digits making up that number are the numbers of the rows in which to place 8 successive queens.

[avva.livejournal.com]

Да, действительно странно. Ну, может им так больше понравилось.