2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Клетки в таблице
Сообщение17.09.2015, 13:11 
Дана квадратная таблица $n\times n$,при каких $n$ в ней можно выделить некоторое количество клеток так,чтобы в каждой строке стояло одинаковое число выделенных клеток,а в каждом столбце разное? Является ли эта задача стандартной?Если да ,то на какую она тему?Эта задача-обобщение одной олимпиадной ,где таблица была дана при конкретном $n$

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 13:32 
Аватара пользователя
Выглядит довольно стандартной... Кажется, встречалась.
По крайней мере, у вас есть решение для того $n$? Попробуйте его обобщить.

Кстати, может ли в некоторой клетке быть 0 выделенных? Или обязательно не менее одной? (Второй вариант проще!)

Решение, кстати, простое!

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 13:50 
При втором варианте легко подсчитать число клеток в строке, я же хочу понять суть задачи исследовать ее полностью.Эта задача связана с подстановками?

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 13:52 
Аватара пользователя
Да нет! Просто "на подумать". Если для некоторого варианта нет решения -- надо это доказать (чувствую, вы знаете, как)
Если решение есть -- его надо предъявить. И все!

(пробелы)

Не могли бы вы ставить пробелы после точек и запятых? А то плохо смотрится.

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 14:46 
Я получил , что заполнение возможно для любого нечетного $n$, так как для $n=3$ заполнение возможно , при $n+2$, оставляем заполнение для случая $n$ , потом заполняем две нижние строки добавляя по две клетки к каждому столбцу в порядке убывания заполненных клеток в нем, а два правых столбца заполняем числом клеток,которые разделяют минималое и максимальное число заполненных клеток в столбцах слева.Но что делать для четного $n$ , и хотелось бы понять, сколько клеток может быть заполнено для каждого конкретного нечетного $n$.

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 14:49 
kikik в сообщении #1054130 писал(а):
Но что делать для четного $n$

Попытаться разделить $n+1$ пополам.

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 15:15 
ewert в сообщении #1054133 писал(а):
kikik в сообщении #1054130 писал(а):
Но что делать для четного $n$

Попытаться разделить $n+1$ пополам.
Соединяя таблицы , можно получить,что условие выполняется для $n$, не являющихся степенью двойки ,а как доказать невозможность заполнения ,если $n$ степень двойки?

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 15:24 
provincialka в сообщении #1054106 писал(а):
Кстати, может ли в некоторой клетке быть 0 выделенных? Или обязательно не менее одной?

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 15:25 
Может

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 16:59 
Аватара пользователя
Если "может", то ответ положительный для любого $n$. Нужно ли еще что-то пояснять? Решение понятно?

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 17:46 
А теперь надо определить возможное число выделеных клеток при каждом $n$

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 18:37 
Аватара пользователя
Ну, уж это легко! Во всех клетках может быть минимум $0+1+... +(n-1)$ и максимум $1+2+... + n$ отмеченных. Причем количество должно делиться на $n$ (понимаете, почему?)

-- 17.09.2015, 18:49 --

Разве степень двойки не подходит?
$n=4$
$$\begin{bmatrix}
 X & X &. &.\\
 X &  X& .&.\\
 X &  X& .&.\\
 X & . &X &.
\end{bmatrix}$$

 
 
 
 Re: Клетки в таблице
Сообщение17.09.2015, 18:53 
Спасибо,разобрался

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group