Задача на спички

[ole-ole-ole]

Подскажите, пожалуйста, идею! Я свои мысли написал ниже:

Изначально на столе лежит куча из 2008 спичек. За ход можно выкинуть из какой-либо кучки 1 спичку, после чего разделить одну из кучек на две. Выкидывать из кучки последнюю спичку нельзя. Могут ли через несколько ходов на столе остаться только несколько кучек из 3 спичек каждая?

Вот мы изначально выкинули одну спичку. Разделили на две кучки $2008-4$ и 3, далее $2008-4\cdot 2$ и две кучки по $3$, $2004-3\cdot 3$, три кучки по $3$, в общем виде $2008-4k$ и $k$ кучек по $3$.

И вроде как сходится $2008-4k+k+3k=2008$. Значит может остаться?

[grizzly]

ole-ole-ole в сообщении #1034838 писал(а):

Значит может остаться?

Какой там у Вас последний ход получился?

[Cash]

Инвариант найдите.

[ole-ole-ole]

$2008-4k\ge 0$, значит $k\le 502$. Значит последний ход при $k=512$, будет $0$ и $512\cdot 3$. Верно? А что за инвариант такой?

[Legioner93]

ole-ole-ole
Какое число не меняется после совершения хода? Ну самое очевидное.

[Cash]

Неверно.
Инвариант - это один из приемов решения задач про игры и не только. Игра Баше, Ним и пр.
Начальные сведения можно, например, здесь посмотреть.
http://kvant.mccme.ru/1976/02/poisk_invarianta.htm

Upd. Теория может и лишняя и см. сообщение Legioner93

[ole-ole-ole]

Legioner93 в сообщении #1034866 писал(а):

ole-ole-ole
Какое число не меняется после совершения хода? Ну самое очевидное.

Суммарное количество спичек

-- 08.07.2015, 22:56 --

Cash в сообщении #1034871 писал(а):

Неверно.
Инвариант - это один из приемов решения задач про игры и не только. Игра Баше, Ним и пр.
Начальные сведения можно, например, здесь посмотреть.
http://kvant.mccme.ru/1976/02/poisk_invarianta.htm

Upd. Теория может и лишняя и см. сообщение Legioner93

Хорошо, почитаю, спасибо!

[Cash]

Оно на 1 уменьшается с каждым ходом.

[ole-ole-ole]

Число $4$ и число $3$ тут постоянны. Ну и убывает на $4-3=1$ после каждого хода

[Legioner93]

Инвариант вы должны скомбинировать из следующих величин (больше не из чего): $N$ спичек, поделённые на $K$ кучек по $n_1, n_2, \cdots n_K$ спичек в кучках.

Если сразу не можете, то сделайте несколько произвольных ходов и выпишите все эти числа. И смотрите на них методом внимательного глаза.

[Cash]

ole-ole-ole в сообщении #1034877 писал(а):

Число $4$ и число $3$ тут постоянны.

Вообще-то 3 - это совершенно не обязательно.

[ole-ole-ole]

Все равно не получается найти инвариант, как будто все меняется.

Вот как раз несколько ходов:

Вот мы изначально выкинули одну спичку. Разделили на две кучки $2008-4$ и 3, далее $2008-4\cdot 2$ и две кучки по $3$, $2004-3\cdot 3$, три кучки по $3$, в общем виде $2008-4k$ и $k$ кучек по $3$.

За $k$ ходов суммарное число спичек будет $2008-k$ и это числ должно делится на $3$. Тогда $2008-k=3n$. Решая уравнение в целых числах, имеем $k=3m+1$, $n=669-m$. Пока что других идей нет, к сожалению

[grizzly]

ole-ole-ole
Дались Вам эти "$k=3m+1$". Никто ведь в условии задачи не говорил, что обязательно нужно только делить. Но раз Вам так хочется, пусть. Только ответьте, пожалуйста, подробно без всяких формул, что Вы будете делать, когда у Вас останется 12 спичек на главной кучке и много кучек по 3.

(Лучше всего найдите реальные спички для начала -- 12 штук. А то я Вам уже как-то этот вопрос задавал раньше, так Вы за формулы спрятались, а свою ошибку так и не поняли.)

[ole-ole-ole]

Когда 12 спичек осталось и остальные сгруппированы по три, получается, что можно выкинуть 1 спичку и разбить на кучки 3 и 8. Из 8 выкинуть 1 спичку, разбить 7 на две кучки 4 и 3, из 4 выкинуть одну спичку. Получается 3 спички выкинули и три кучки по три спички.
Значит число 2008 должно быть кратно 12. Но это не так, значит разбить нельзя. Верно?

[grizzly]

ole-ole-ole в сообщении #1035606 писал(а):

из 4 выкинуть одну спичку.

Такой ход недопустим. Вы после отбрасывания одной спички обязаны разделить кучку на 2 части.