Тег «комбинаторика»

Одна комбинаторная задача

10 Октябрь 2013, 22:19

Интересная комбинаторная задача из книги
László Babai, Péter Frankl, Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science, Preliminary Version 2 (September 1992), The University of Chicago.

В городе

    \[n\]

жителей. Они любят создавать клубы, маленькие и большие, это основная их деятельность. В городе изданы законы, регулирующие образование таких клубов:

1) В каждом клубе может быть только нечетное число членов.
2) Каждые два клуба имеют четное число общих членов.

Какое максимальное число различных клубов может быть создано в этом городе?

Довольно простое и красивое решение этой задачи получается, если воспользоваться методами линейной алгебры. Читать полностью ‘Одна комбинаторная задача’ »

Теги: , ,
Рубрика: Разные задачи  |  Отзывов: 3

Рождественская лотерея

26 Декабрь 2012, 0:04

Это еще одна задачка, предложенная El País.

С 2011 года проводится Рождественская лотерея, в которой разыгрываются призы между сто тысячью билетов с номерами от

    \[00000\]

до

    \[99999\]

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

В нашем случае лотерейный номер будет считаться красивым, если его номер отвечает одному и только одному из следующих трех условий:
а) делится на

    \[5\]

,
б) дает в остатке

    \[2\]

при делении на

    \[7\]

,
в) сумма его цифр делится на

    \[9\]

. Читать полностью ‘Рождественская лотерея’ »

Теги: ,
Рубрика: Разные задачи  |  Ваш отзыв

Число перестановок

21 Ноябрь 2012, 0:02

Задача. Чему равно число таких перестановок

    \[(a_1,a_2,\ldots,a_n)\]

чисел

    \[(1,2,\ldots,n)\]

, которые удовлетворяют условию

    \[a_k\ne k\]

при всех

    \[k\]

?

Это довольно известная задача, она встречается в разных формулировках, например, такой:

Несколько человек решили подарить друг другу подарки на Рождество. Каждый приготовил один подарок и подписал на нем свое имя. Друзья решили распределить подарки случайным образом. Они написали свои имена на листочках бумаги и положили в шапку. Каждый тянет листочек, и если получилось так, что у всех имена на вытащенных ими листках не совпали с их собственными именами (а иначе какой же это подарок — самому себе?), то распределение подарков состоялось. Сколькими различными способами могут распределиться подарки между друзьями?

Показать решение

Теги: ,
Рубрика: Разные задачи  |  Отзывов: 2

О треугольнике Паскаля

15 Июль 2012, 0:02

Числовые треугольники имеют довольно много различных свойств. И задач, связанных с ними, известно достаточно много. Но вот мне недавно попалось еще одно свойство известного треугольника Паскаля. Надеюсь, вам тоже понравится ;)

Довольно интересные треугольники являются частями треугольника Паскаля. Все числа, из которых они состоят, делятся на одно и то же число. Удивительно, что делимость прослеживается только на простые числа

    \[p\]

. Читать полностью ‘О треугольнике Паскаля’ »

Теги: ,
Рубрика: Развлекалочки ;)  |  Отзывов: 3

Задача с монетами

16 Май 2012, 0:05

Это достаточно красивая и интересная, на мой взгляд, задача.

На столе лежат 16 монет, составляющих квадрат

    \[4\times4\]

. Часть из этих монет лежит вверх орлом, а часть — решкой. Монеты можно переворачивать по следующим правилам: можно перевернуть все монеты, находящиеся в одном горизонтальном ряду, в одном вертикальном ряду или на одной диагонали (если монета лежит в углу, она образует диагональ из одной монеты). Целью игры является перевернуть все монеты вверх либо орлом, либо решкой. Всегда ли возможно это сделать или существуют некоторые расположения монет, для которых это невозможно? Читать полностью ‘Задача с монетами’ »

Теги: ,
Рубрика: Разные задачи  |  Отзывов: 5

Полуинвариант

9 Май 2012, 0:02

Наряду с задачами на инвариант, на олимпиадах довольно часто встречаются и задачи на полуинвариант. Полуинвариант — это некоторая величина, которая в отличие от инварианта не остается неизменной, а увеличивается или уменьшается и может принимать при этом лишь конечное число различных значений.

Лучше всего рассмотреть, как решать такие задачи, на примерах.

Задача 1. В квадрате

    \[20\times20\]

стоят

    \[400\]

ненулевых чисел. Можно изменить знак у всех чисел, стоящих в одном столбце или в одной строке. Докажите, что за конечное число таких операций можно добиться того, что сумма чисел, стоящих в любой строке или в любом столбце, будет неотрицательной. Читать полностью ‘Полуинвариант’ »

Теги: , ,
Рубрика: Статьи по математике  |  1 отзыв