Есть такая затягивающая игра — Entanglement. С недавнего времени она входит в поставку Google Chrome (начиная с девятой версии). Однако пост не о этом. Игровое поле состоит из шестиугольников, на сторонах которых есть 12 точек соединенных попарно. Захотелось мне посчитать количество возможных разных шестиугольников (т.е. тех, которые отличаются хотя бы одной линией). В общем, у меня хватило ума определить, что данный вопрос решается комбинаторикой, я даже определил, что всего может быть 66 разных линий (С212), могу определить С666, но это не то. Я не знаю как задать условие, когда из одной точки может входить/выходить только одна линия. В общем, как эти шестиугольники посчитать, а?

размер 181x158, 5.82 kb

GD Star Rating
loading...

15 Responses to Как посчитать шестиугольники?

  1. BoBam:

    количество комбинация будет равно количеству перестановок из (n*m — 1)! — где n — количество граней, а m — количество точек на одной грани.
    можно доказать очень просто, пусть конфигурация шестиугольника задается строкой s = {s0, s1,.. s(m*n)}, где si — номер точки, с которой соединена i–я точка. Она может быть соединена с любой точкой, кроме себя самой. Тогда, для выбора 1–го элемента у нас есть n*m–1 возможностей, для выбора 2–го — n*m — 2, n*m–го — 1. Поэтому, количество возможных шестиугольников будет равно (n*m — 1)*(n*m — 2)*(n*m — 3)… = (n*m — 1)!

  2. Woen:

    Спасибо!

  3. BoBam:

    а ведь не правильно посчитал, нужно еще учесть, что если у нас в i–ой позиции строки находится число sj, то в j–й позиции должно быть si. Получается, что у нас будет строка s = {s1, s2,..sk} где k = m*n/2. Если si = j, то i–я точка, соединена c j–й точкой j принадлежит отрезку [k + 1.. m*n]. Тогда получается, что количество комбинаций будет равно (m*n/2)!.

  4. Woen:

    ну, 720 вариантов лучше чем 39916800. 🙂

  5. Peels:

    У меня получилось 20790, не учитывая симметрии поворота и отражения шестиугольника.

  6. Peels:

    Ой, обсчитался. 10395.

  7. Peels:

    Посчитал на компутере. С точностью до поворота бывает всего 1799 разных фишек.

  8. 6Doctor:

    А как это она входит в поставку? В браузер теперь «входят» игры? ничо не понимаю.

  9. Peels:

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

  10. 6Doctor:

    лады, где искать игру в Хроме 9? (:

  11. Ezin:

    я нашел такую ссылку и ткнул установить. Оно потупило и установило(во вкладку новой вкладки, когда не открыта страница). Страничка, которую дал автор поста не грузилось ничего.

  12. 6Doctor:

    забавно, перехожу в хроме по ссылке и справа написано «Installed». Но я ничего не ставил — а просто играл по ссылке автора. Там все работает (: Игруха интересная.

  13. Ezin:

    А когда откываешь новую пустую вкладку — у тебя не высвечивается таблица частопосещаемых, таблица недавно закрытых и таблица с приложениями?

  14. 6Doctor:

    омазафака! хрени появились, и правда. Только обновил Хром до 9–ки, еще не видел. А теперь — ПРОЗРЕЛ.

  15. Ezin:

    Я сам прозрел. Только у меня хром 8.0.сколько–то там.

Добавить комментарий