ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 24 25 26 27 28 29 30 >> [Всего задач: 206]      



Задача 98107

Темы:   [ Числовые таблицы и их свойства ]
[ Простые числа и их свойства ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4
Классы: 8,9

Можно ли в таблицу 4×4 расставить такие натуральные числа, что одновременно выполняются следующие условия:
  1) произведения чисел, стоящих в одной строке, одинаковы для всех строк;
  2) произведения чисел, стоящих в одном столбце, одинаковы для всех столбцов;
  3) среди чисел нет равных;
  4) все числа не больше 100?

 

Решение

Рассмотрим греко-латинский квадрат (таблица слева). В нём каждая буква встречается в каждой строке и каждом столбце ровно один раз, и все 64 пары букв в клетках – разные.

Подставив вместо этих восьми букв взаимно простые числа и вычислив соответствующие произведения в клетках, получим таблицу, удовлетворяющую первым трём условиям. А если  A = a = 1,  B = 2,  C = 3,  D = 5;  b = 7,  c = 11,  d = 13,  то и четвёртое условие выполнено (см. таблицу справа).

Ответ

Можно.

Прислать комментарий

Задача 98139

Темы:   [ Числовые таблицы и их свойства ]
[ Полуинварианты ]
[ Алгебраические неравенства (прочее) ]
[ Классические неравенства (прочее) ]
Сложность: 4
Классы: 8,9

Автор: Иванов С.

Дана таблица n×n, заполненная числами по следующему правилу: в клетке, стоящей в i-й строке и j-м столбце таблицы записано число     В таблице зачеркнули n чисел таким образом, что никакие два зачёркнутых числа не находятся в одном столбце или в одной строке. Докажите, что сумма зачёркнутых чисел не меньше 1.

Решение

  Сумма чисел, стоящих в левой верхней и правой нижней вершинах любого прямоугольника, больше суммы чисел, стоящих в других двух вершинах:
  Действительно, это неравенство имеет вид


  Если в левой нижней клетке таблице число не зачеркнуто, то берем зачеркнутые числа, стоящие в первом столбце и n-й строке, рассматриваем прямоугольник, диагональ которого они образуют и заменяем их на числа, стоящие в других двух вершинах прямоугольника. При этом сумма зачеркнутых чисел уменьшится, а в левой нижней клетке таблицы появится зачеркнутое число. Выкинув из таблицы первый столбец и n-ю строку, повторим процедуру с уменьшенной таблицей и т. д.
  В результате получим таблицу, в которой зачеркнуты все числа по диагонали, ведущей из левого нижнего в правый верхний угол.
Сумма этих чисел равна 1.

Прислать комментарий

Задача 98528

Темы:   [ Числовые таблицы и их свойства ]
[ Раскладки и разбиения ]
[ Доказательство от противного ]
[ Принцип крайнего (прочее) ]
[ Процессы и операции ]
Сложность: 4
Классы: 10,11

Даны две таблицы A и B, в каждой m строк и n столбцов. В каждой клетке каждой таблицы записано одно из чисел 0 или 1, причём в строках таблиц числа не убывают (при движении по строке слева направо), и в столбцах таблиц числа не убывают (при движении по столбцу сверху вниз). Известно, что при любом k от 1 до m сумма чисел в верхних k строках таблицы A не меньше суммы чисел в верхних k строках таблицы B. Известно также, что всего в таблице A столько же единиц, сколько в таблице B. Докажите, что при любом l от 1 до n сумма чисел в левых l столбцах таблицы A не больше суммы чисел в левых l столбцах таблицы B.

Решение

Предположим противное. Рассмотрим наименьшее l, при котором сумма l левых столбцов A превзошла аналогичную сумму B. Тогда в l-м столбце число нулей в A (обозначим его k) меньше, чем в B. Разрежем каждую из таблиц двумя перпендикулярными прямыми на 4 прямоугольные части (угла), отделив l столбцов слева и k строк сверху (см. рис. для таблицы A, где "зона единиц" показана темным). Сравним суммы в углах. В левых верхних углах обеих таблиц единиц, очевидно, нет. Поэтому сумма в левом нижнем углу равна сумме в l левых столбцах, и у A она больше по построению. Аналогично, сумма в правом верхнем углу равна сумме в k верхних строках, и у A она не меньше по условию. Наконец, правый нижний угол A целиком заполнен единицами, поэтому сумма там не меньше. В итоге в А единиц оказывается больше, чем в B. Противоречие.

Прислать комментарий

Задача 98625

Темы:   [ Числовые таблицы и их свойства ]
[ Правило произведения ]
[ Инварианты ]
[ Линейная и полилинейная алгебра ]
Сложность: 4
Классы: 10,11

В каждой клетке таблицы размером 4×4 стоит знак "+" или "-". Разрешено одновременно менять знаки на противоположные в любой клетке и во всех клетках, имеющих с ней общую сторону. Сколько разных таблиц можно получить, многократно применяя такие операции?

Решение

  Будем считать, что в каждой клетке находится кнопка, нажимая на которую мы меняем знак в этой клетке и во всех соседних. Заметим, что нажимая кнопки во второй строке мы можем привести в произвольное состояние первую строку (каждая кнопка меняет знак в клетке над ней и не меняет состояние остальных клеток первой строки). После этого, нажимая кнопки в третьей строке, мы можем получить произвольный набор знаков во второй строке, и наконец, нажимая кнопки четвёртой строки, получить произвольную третью строку. Итак, из любой таблицы можно получить не менее 212 различных таблиц (отличающихся уже в первых трёх строках).
  Приведём два способа получить оценку сверху.

  Первый способ. Изначально у нас есть 16 кнопок. Назовем 12 кнопок в белых клетках основными, а 4 в закрашенных – вспомогательными (см. рис.). Результата от нажатия вспомогательной кнопки можно достичь, нажав вместо этого несколько основных (для верхней вспомогательной кнопки – это основные кнопки, помеченные точками; для остальных трёх вспомогательных кнопок нужный набор основных получается поворотами рисунка на 90°, 180° и 270°).
  Итак, если таблицу можно получить, то достаточно последовательности нажатий основных кнопок. Ясно, что результат не зависит от порядка нажатий кнопок. Поэтому пару нажатий на одну и ту же кнопку можно выкинуть. В итоге оставшиеся в последовательности кнопки будут нажаты по разу. Итак, каждой искомой таблице соответствует набор основных кнопок, нажатием которых она получается. Но таких наборов (а, значит, и таблиц) не более 212.

  Второй способ. Легко проверить, что каждая операция меняет состояние чётного числа из помеченных точками клеток. Поэтому чётность количества плюсов на помеченных клетках остается той же, что и в исходной таблице A. Тем самым знак в закрашенной помеченной клетке определяется чётностью количества плюсов в помеченных незакрашенных клетках.
  Поворачивая рисунок на 90°, 180° и 270° убеждаемся в том, что знаки в четырёх закрашенных клетках полученной после операций таблицы полностью определяются остальными 12 знаками (расположенных в незакрашенных клетках) этой таблицы (и исходной таблицей A). Это означает, что из A можно получить не более 212 различных таблиц.

Прислать комментарий

Задача 109824

Темы:   [ Числовые таблицы и их свойства ]
[ Упорядочивание по возрастанию (убыванию) ]
[ Неравенство Коши ]
Сложность: 4
Классы: 8,9,10

В таблице 2×n расставлены положительные числа так, что в каждом из n столбцов сумма двух чисел равна 1. Докажите, что можно вычеркнуть по одному числу в каждом столбце так, чтобы в каждой строке сумма оставшихся чисел не превосходила  n+1/4.

Решение

Пусть в верхней строке стоят числа a1, a2, ..., an. Переставив столбцы, можно считать, что  a1a2 ≤ ... ≤ an.  Тогда в нижней строке стоят соответственно b1 = 1 – a1b2 = 1 – a2,  ...,  bn = 1 – an;  ясно, что  b1b2 ≥ ... ≥ bn.  Если  a1 + a2 + ... + ann+1/4,  то вычеркнем все числа нижней строки. Иначе найдём такой минимальный номер k, что  a1 + a2 + ... + an > n+1/4,  вычеркнем в верхней строке числа ak, ak+1, ..., an, а в нижней – b1, b2, ..., bk–1. По выбору k  a1 + ... + ak–1n+1/4. Поскольку     то и

   
Прислать комментарий

Страница: << 24 25 26 27 28 29 30 >> [Всего задач: 206]      



© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .