Канадские загадки
Гостил у сына в Монреале и увидел в местной газете неизвестную мне загадку (они ее binaire называют). Пишут, она возникла в Японии, оттуда перекинулась в Бельгию-Голландию, оттуда во Францию, теперь попала в Квебек, но дальше по континенту пока почему-то не пошла.
Есть квадрат 2Nx2N; в каждой строке и столбце N единиц и N нулей, все строки и столбцы уникальны, и в них не может быть более, чем два одинаковых символа подряд. Большинство символов стирают, и надо восстановить таблицу. Тут примеры
http://www.binarypuzzle.com/
Расторопные европейские математики уже навели теорию, как решать такие загадки
https://link.springer.com/content/pdf/10.1007%2Fs11786-017-0322-4.pdf
Сам я ничего лучше, чем backtrack-based search (= б/м тупой перебор) не придумал. По-моему, предложенное решение с переложением на язык полиномов и использование базиса Гребнера очень изящно.
***
Давно не ездил по Канаде: все вспоминал любимое стихотворение
Sweet maiden of Passamaquoddy,
Shall we seek for communion of souls
Where the deep Mississippi meanders,
Or the distant Saskatchewan rolls?
Ah, no! in New Brunswick we'll find it -
A sweetly sequestered nook -
Where the swift gliding Skoodoowabskooksis
Unites with the Skoodoowabskook.
Meduxnakik's waters are bluer;
Nepisiguit's pools are more black;
More green is the bright Oromocto,
And browner the Peticodiac.
But colours more radiant, in Autumn,
I see when I'm casting my hook,
In the waves of the Skoodoowabskooksis,
Or perhaps in the Skoodoowabskook.
etc. http://www.heirloomsreunited.com/2010/08/poem-maiden-of-quoddy-by-james-de-mille.html
Почему в викторианские времена была обсессия с непроизносимыми индейскими названиями? Я еще там понимаю про Чикаго в Иллиное, но ведь там такие села, что о них сломал язык бы даже гордый Гайвата, бесполезны ему б были рукавицы минджикэвон и тяжелый томагаук + дубинка поггэвогон...
***
К слову о географии, подумал - "над Канадой небо синее, меж берез дожди косые // хоть похоже на Россию, только все же не Россия" - докудова, интересно, добрался автор песни, чтоб такое написать на трезвую голову? Проверил - оказалось, Галифакс. Где ж в России похожие места-то?
Есть квадрат 2Nx2N; в каждой строке и столбце N единиц и N нулей, все строки и столбцы уникальны, и в них не может быть более, чем два одинаковых символа подряд. Большинство символов стирают, и надо восстановить таблицу. Тут примеры
http://www.binarypuzzle.com/
Расторопные европейские математики уже навели теорию, как решать такие загадки
https://link.springer.com/content/pdf/10.1007%2Fs11786-017-0322-4.pdf
Сам я ничего лучше, чем backtrack-based search (= б/м тупой перебор) не придумал. По-моему, предложенное решение с переложением на язык полиномов и использование базиса Гребнера очень изящно.
***
Давно не ездил по Канаде: все вспоминал любимое стихотворение
Sweet maiden of Passamaquoddy,
Shall we seek for communion of souls
Where the deep Mississippi meanders,
Or the distant Saskatchewan rolls?
Ah, no! in New Brunswick we'll find it -
A sweetly sequestered nook -
Where the swift gliding Skoodoowabskooksis
Unites with the Skoodoowabskook.
Meduxnakik's waters are bluer;
Nepisiguit's pools are more black;
More green is the bright Oromocto,
And browner the Peticodiac.
But colours more radiant, in Autumn,
I see when I'm casting my hook,
In the waves of the Skoodoowabskooksis,
Or perhaps in the Skoodoowabskook.
etc. http://www.heirloomsreunited.com/2010/08/poem-maiden-of-quoddy-by-james-de-mille.html
Почему в викторианские времена была обсессия с непроизносимыми индейскими названиями? Я еще там понимаю про Чикаго в Иллиное, но ведь там такие села, что о них сломал язык бы даже гордый Гайвата, бесполезны ему б были рукавицы минджикэвон и тяжелый томагаук + дубинка поггэвогон...
***
К слову о географии, подумал - "над Канадой небо синее, меж берез дожди косые // хоть похоже на Россию, только все же не Россия" - докудова, интересно, добрался автор песни, чтоб такое написать на трезвую голову? Проверил - оказалось, Галифакс. Где ж в России похожие места-то?