Сколько наборов параметров нужно проверить для линейности

[mandarin91]

Есть задача, точнее вопрос (там ничего не надо считать, а просто подумать и написать ответ)
Условие такое:
Имеется "чёрный ящик", вычисляющий функцию f от n переменных. На скольких наборах надо вычислить значения функции, чтобы проверить, что она нелинейна?

(Имеется ввиду следующее: есть пустая таблица от n переменных (т.е. вписаны наборы, но не вписаны значения)

Выбираем какой-то набор и "кладем" его в ящик, выдается значение функции. Вопрос этой задачи -- после скольких наборов вы сможете точно сказать, что функция нелинейна, какова бы она не была?)

загвоздка в том, что я не помню критерий линейности (можно по многочлену Жегалкина. но он тут не нужен), скажите пожалуйста этот критерий или вообще ответ! огромное спасибо!! )))

[Ираклий]

Выберем какую-нибудь линейную функцию. Построим по ней другую функцию, совпадающую с выбранной всюду, кроме одного набора параметров. А на этом наборе параметров она от неё отличается. Но какой именно это набор параметров, нам не известно. Пусть построенная функция и есть та функция, которую мы проверяем на линейность методом "черного ящика". Сколько попыток нам придется сделать для установления нелинейности в "наихудшем" случае?

[mandarin91]

Именно... Но спасибо, я разобрался, ответ тривиален, на всех наборах, т.е. на $2^n$, т.к. если функция линейна она имеет четное количество единиц (либо ни одного, как исключение), и если нам не будет известно хотя бы одно значение, мы не сможем определить линейность/нелинейность.