2 дек. 2014 г.

Двоичные немагические прямоугольники

Добрый день.

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

У двоичной матрицы NxM (т.е. в ячейках которой только нули и единицы) мы можем посчитать N сумм значений в строках и M сумм значений в столбцах. Эти суммы иногда могут однозначно задавать матрицу. Например, суммы [1,2,0][2,1] могут быть только у следующей матрицы:
     1 0
     1 1
     0 0

Но иногда суммы задают не одну матрицу. Например, суммы [1,1,2][2,2] соответствуют следующим двум матрицам:
     0 1     1 0
     1 0     0 1
     1 1     1 1

Декабрьское задание состоит в поиске таких сумм, которые описывают ровно 29 разных двоичных матриц. Чтобы исключить тривиальные решения, наложим ещё одно ограничение: матрица должна содержать не более 50 бит. В качестве решения принимаются две строки: в первой N целых чисел и во второй M целых чисел. Произведение N*M должно быть не больше 50.


Если вам интересен такой класс задачек, то давайте поделимся друг с другом в комментариях ответами на следующие вопросы:
1) Придумали ли вы тривиальное решение (более 50 бит, на которое намекают авторы задачи)?
2) Какие количества двоичных матриц вы умеете выражать преложенным способом (в условии задачи есть решения для 1 и 2, а спрашивается про 29, но ведь есть ещё много других чисел)?
3) Придумали ли вы способы «умножать» ранее найденное решение (т.е. получать наборы сумм, описывающих N*k матриц, имея решение для N матриц)?
4) Нашли ли вы решение для 29 матриц и небольшого их размера? Если да, то можете вписать своё имя на сайт IBM, отправив им своё решение (каждый месяц несколько десятков человек пользуются этой возможностью)

Хорошей недели и интересных задачек!

3 комментария:

  1. Анонимный03.12.2014, 8:12

    1) Да, получить любое число матриц N можно, если их размер 2*(N+1). Для 60 бит решение есть, а для 50 пока нет.
    2) Тривиальное решение позволяет выразить любое количество матриц. Чуть менее тривиальное решение даёт мне число сочетаний: 3, 4, 6, 10, 15, 20, 21, 28, 35... (частным случаем этого решения является набор всех натуральных чисел из первого пункта)
    3) Пока нет.
    4) Нет.

    ОтветитьУдалить
  2. Приятно видеть, что сайт Ильи Весеннего вернулся к жизни.

    Поздравляю всех с наступающим Новым годом, и в качестве подарка предлагаю около новогоднюю задачку. Задан полином Р(х) пятого порядка; известно, что:

    Р(2014) = 1
    Р(2015) = 2
    Р(2016) = 3
    Р(2017) = 4

    Чему равно значение Р(2013)?

    ОтветитьУдалить
    Ответы
    1. Артур, спасибо за поздравления и задачку!

      Удалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний