ОФФ Задачка для 6-го класса

Форум 1С: Одинэс.Ру
Найти!

ОФФ Задачка для 6-го класса

Путевый лист
10.03.2009 - 07:37
 Даны три кучки камней
Всегда ли можно за конечное число ходов уравнять какие-либо две кучки
Ход: переложить с одной кучки столько же сколько во второй
Вот такая задача!!!
К списку тем 1 2 3 4 > К списку форумов

Интересные темы

odines.ru
21.11.2024 - 17:58
 Смотри также:
Как поставляется документация по встроенному языку с 1С 8?
вспомните сегодня Дядю Колю, люди!
ОФФ: Анимация, или бессонница.

Re: ОФФ Задачка для 6-го класса

Блондинка в шок
150 - 12.03.2009 - 10:31
 Кста, предложенный алгоритм чуть-чуть неверный. Не так сформулировала.  

Re: ОФФ Задачка для 6-го класса

roma n
151 - 12.03.2009 - 11:36
 например, после перекладывания стало А=19, Б=42, С=2; Получили Б>(А+С)
Шаг2. Откладываем большую кучку (Б) в сторону, она пока не нужна...
Займемся перекладыванием в двух оставшихся.
Сумму двух оставшихся можно представить в виде двоичного числа.
(А+Б=21=0010101) или в виде двоичного ряда с коэффициентами. 1*2^4+0*2^3+1*2^2+0*2^1+1*2^0.
Поскольку при перекладывании между А и С мы всегда производим операции удваивания и вычитания, обязательно получается момент, когда в одной из кучек будет число, равное наименьшей степени двойки со значащим коэффициентом=1. - вот тут ошибаешься. НОД вклинивается.
Пример с той же суммой 21
7 - 14

Re: ОФФ Задачка для 6-го класса

Исчо
152 - 12.03.2009 - 12:32
 (145)О, Чучундер внял моим молитвам о весовой природе камней. Чучундер, давай искать решение в направлении  подбора весовых коэффициентов!

Re: ОФФ Задачка для 6-го класса

Блондинка в шок
153 - 12.03.2009 - 17:32
 (151) - ужу сама знаю. см.(150) :))
 
кста - если одна из кучек ровно вдвое больше другой ( у тебя - 7/14) - это второй вырожденный случай. В этом случае решение заканчивается в один ход.
если хочешь покритиковать более корректно - то с тем же 21 - возьми 18 и 3.
18-3
15-6
9-12
18-3
 
но в общем идея Шага3 от этого не меняется.
В Шаге3 алгоритма ошибки были замечены? нет? значит, пока считаем это шаг корректным.
И вообще ... эй, мужчины. Я набросала "рыбу", в надежде, что вы способны самостоятельно приготовить уху...
 

Re: ОФФ Задачка для 6-го класса

Путевый лист
154 - 12.03.2009 - 19:00
 (ВСЕМ) Конечно все это интересно. Но я-то вообще имел в виду некую формулу для
1-ая кучка m камней
2-ая кучка n камней
3-ая кучка k камней
Все числа конечны. И найти это самое количество перекладываний в буквенном виде, зависящее (от m,n,k). Вот только тогда задача будет решена как мне кажется
И опять же Задачка для 6-го класса. Ну не пахнут все эти решения 6-м классом Тянут на нобелевку

Интересные темы

odines.ru
21.11.2024 - 17:58
 Смотри также:
На чем вести большую базу ?
OFF Положим начало хорошему делу? Рапортую: Дочь. 3.860/54
ОФФ: Май

Re: ОФФ Задачка для 6-го класса

Блондинка в шок
155 - 12.03.2009 - 19:22
 (154) неправ, имхо.
чудится мне, решение задачки не будет иметь стройной формулы f(m,n,k). А будет просто некая цепочка логических рассуждений. Возможно, в каких-то местах цепочка будет подкрепляться отдельными формулами.
 
ps: Логических рассуждений на уровне подготовленного шестиклассника. :)

Re: ОФФ Задачка для 6-го класса

2Green
156 - 12.03.2009 - 21:34
 ну если надо f(m,n,k), то
x+y+z=n
задаёт плоскость в трехмерной системе координат.
это всё. к решению не приблизились ни на йоту.

Re: ОФФ Задачка для 6-го класса

Путевый лист
157 - 12.03.2009 - 21:51
 (154) Огромное спасибо, но остальные 7 задач имеют однозначное либо алгоритмическое либо логическое решение, либо их смесь, но решение однозначно, может быть за исключением первой которое находится методом подбора за 5 минут. А эта задача либо попала туда по ошибке либо мы все тупим и есть какое-то однозначное решение с хотя бы интуитивно понятнным 6-класснику объяснением. Вот его-то пока я не увидел и сам не нашел

Re: ОФФ Задачка для 6-го класса

Путевый лист
158 - 12.03.2009 - 21:53
 И именно поэтому я вышел на форум. Остальные-то мы решили. А эта как кость в горле

Re: ОФФ Задачка для 6-го класса

Чучундер
159 - 13.03.2009 - 00:53
 (158) интересно послушать у математичик в 6 классе - 1.правильно ли мы поняли задачу 2. какона все-таик решается в 6 классе.

Re: ОФФ Задачка для 6-го класса

Исчо
160 - 13.03.2009 - 05:40
 А может попробовать провести ролевую игру на природе? В мае, всем форумом, поедем на шашлыки, выпьем пивка, наберем камней, и будем бегать с ними между кучками! А?

Re: ОФФ Задачка для 6-го класса

roma n
161 - 13.03.2009 - 05:41
 (155) +1
Вряд-ли задача имеет решением формулу. Алгоритм - возможно, но не обязательно.
(157) возможен финт с переформулировкой задачи (например в геометрическую - 3 метки на окружности или обратную как в (138) и т.п.) или допущение "отрицательных" камней. Но на вскидку ничего не приводит к логическому обоснованию решения. Индукция? Тоже вряд-ли...
(153) дело не в том что там ошибка. Можно переформулировать, что в результате манипуляций получим НОД*2^k. Но это утверждение само требует доказательства. А вобще разложение по степеням двойки - идяе. Надо её покурить

Re: ОФФ Задачка для 6-го класса

roma n
162 - 13.03.2009 - 05:52
 +(104) давным-давно знакомый препод по математике повторял: "ищите то, что не меняется"
На роль инварианта вижу
- общее количество камней
- НОД
- четность
Но это мало продвигает вперед...

Re: ОФФ Задачка для 6-го класса

Путевый лист
163 - 13.03.2009 - 06:30
 (161,162,153) Ну да получается, что каждый раз количество камней в кучке в которую перекладывают - удваивается. Но ведь из нее тоже могут перекладывать - тогда удвоится в другой, а в этой просто уменьшится. В-общем, начинаю потихоньку думать сам. Зацепило по-настоящему. Минусовые количества в кучках изначально не рассматриваю. Вопрос-то стоит именно в кнечности операций по перекладыванию. Может быть мы просто какой-то очевидный способ доказательства просто не видим???

Re: ОФФ Задачка для 6-го класса

roma n
164 - 13.03.2009 - 07:01
 (163) не, минусовые количества в кучках быть не могут по смыслу задачи, но это допущение может упростить доказательство (равно как может и не упростить)... это я так, для примера :)

Re: ОФФ Задачка для 6-го класса

DVV
165 - 13.03.2009 - 08:26
 Мне тоже чето кажется, что копать надо в сторону четности.
изначально есть x+y+z, где x<y<z
которые можно преобразовывать в
(z-y)+2y+x или (z-x)+y+2x или z+(у-х)+2x,
что в итоги приведет к 2m+n.
где 2m может быть даже равно 2x или 2y, но что более важно 2m(x,y) всегда четно, а n может быть четным или нет, и нам надо показать эту возможность при различным вариантах четности x,y,z

Re: ОФФ Задачка для 6-го класса

Vacony
166 - 13.03.2009 - 08:43
 0 - есть ли в условии задачи намек про отрицательные числа ?
1.Любое число можно представить в виде 2н+м .
2. мы имеем x + y + z
3. при любом ходе мы получим 2х+y + (z-x)
4. мы имеем выражение (2х+y) и (z-x)=Q - отсюда получается что любое Q может быть получено из (2х+y).

Re: ОФФ Задачка для 6-го класса

Блондинка в шок
167 - 13.03.2009 - 18:49
 Ну тогда еще подброшу. На уровне 6-го класса. (Кстати, НОД и алгоритм Евклида по нахождению НОД изучают, кажется, как раз в 6-м классе. Или в 7-м? так что это далеко не "нобелевка" :) )
 
1. из двух кучек не более чем за один шаг можно сделать, чтобы одна стала в два и более раза больше другой.
(Дано А<B;
Если A>(B/2) тогда A=2A; B=B-A;// Получим B<A/2
Иначе // A<=B/2
КонецЕсли; //что и требовалось
Вывод -> всегда можно добиться, что количество в одной кучке превышает сумму двух других, вместе взятых.
2. Как минимум, из трех две кучки всегда четные, не более, чем за один шаг.
Если А=нечет и B=нечет, тогда А=2А, B=B-A //обе стали четные.
 
Цель вышеизложенного - получить две меньшие четные кучки, а третья (четная или нечетная) всегда будет больше или равна, чем первые две вместе. Зачем нам нужна большая кучка? А чтобы заведомо хватило... потом. ;) Хотя это и необязательно. Вот про четные кучки - важно.
 

(161) Дальше - дальше давай свой НОД (применительно к четным! кучкам) ;)
Если покрутить алгоритм Евклида (а это как раз 6-й класс, не забываем), то можно показать, что, перекладывая две четные друг в друга, мы добьемся комбинации, когда в одной из кучек будет находится такое число, которое будет являться НОД для этой пары (этого шага итерации) четных кучек ;)
 
А дальше - мое разложение по степеням 2.  
Ну или на уровне 6-го класса - если в второй из кучек находится НОД, (а это значит, что первая делится на вторую без остатка - получается целое K, то из третьей (или из первой, тут играет роль чет/нечет K) всегда можно добавить ко второй кратное число раз, чтобы получить первую.
(третья кучка большая, ее на всех хватит ;))
 

 

 

Re: ОФФ Задачка для 6-го класса

Блондинка в шок
168 - 13.03.2009 - 19:01
 Но, как справедливо заметил roma_n, про НОД еще надо доказать.
 
ps: А что, нормальная задача для 6-го класса, с учетом того, что алгоритмы нахождения НОД как раз в этом возрасте и изучают.

Re: ОФФ Задачка для 6-го класса

Anonymous
169 - 15.03.2009 - 18:54
 Друзья! Разрешите и мне вставить пару слов.
Итак, условие (для уточнения, правильно ли понял).
Имеем 3 кучки с разным количеством камней А < B < C.
Можно перекладывать из кучки в кучку к-во камней, равное их числу в одной из кучек. Вопрос: можно ли добиться, чтобы в каких-либо двух кучках было равное число камней? Правильно?
Ответ: можно, например, так.
Решение 1. Переложим все камни из А в С, затем все из В в С.
Получим в кучках А и В равное число камней (равное нулю).
Навел на решение приведенный Геной в (132) пример с собакой и банкой.
Добавим условие, что все камни из кучки перекладывать нельзя.
Тогда Решение 2. Опишу сначала в виде алгоритма.
--
Цикл Пока А <> B
  Если А > B тогда
     А = А-В
     С = С+В
  Иначе
     В = В-А
     С = С+В
  КонецЕсли
Конец цикла
В общем-то всё.  Алгоритм в виде описания:
Перекладываем камни из А в С или из В в С, точнее из бОльшей на момент перекладывания кучки, до тех пор, пока А и В не сравняются.
А они обязательно сравняются, хотя бы на уровне 1 - 1, ведь число камней в них конечно, а кучки будут постоянно уменьшаться.
Задачка, на мой взгляд, действительно, для 6-го класса, поскольку для нахождения алгоритма каких-либо знаний за пределами 6-го класса не нужно.

Re: ОФФ Задачка для 6-го класса

Чучундер
170 - 16.03.2009 - 07:19
 >  из кучки в кучку к-во камней, равное их числу в одной из кучек.
нет, хитрый какой... обсуждаем вариант
из кучки1 в кучку2 к-во камней, равное числу камней в кучке2

Re: ОФФ Задачка для 6-го класса

iogri
171 - 16.03.2009 - 07:26
 Привет всем.
Алгоритм в (140) - это почти решение:
Имеем три кучки камней с количествами (Кучка1)A > (Кучка2)B > (Кучка3)C
Очевидно, что можно записать B = D + k*C (деление с остатком)
Алгоритм такой:
Представим k в двоичном виде (например [100101]). В квадратных скобках будем записывать двоичные числа
Тогда количество камней в кучках запишется так (количество в кучке 1 нас не интересует, важно, что там камней больше чем в кучке 2):
Кучка 1 Кучка 2 Кучка 3
         D + [100101] * C [1] * C
Если последний разряд в числе k = 1, то удваиваем кучку 3 за счет кучки 2:
Кучка 1         Кучка 2 Кучка 3
        D + [100100] * C [10] * C
Если последний разряд в числе k = 0, то удваиваем кучку 3 за счет кучки 1:
Кучка 1 Кучка 2 Кучка 3
         D + [100100] * C [100] * C
Если последний разряд в числе k = 1, то удваиваем кучку 3 за счет кучки 2:
Кучка 1 Кучка 2 Кучка 3
D + [100000] * C [1000] * C
И так далее…
В итоге, получим позицию:
Кучка 1 Кучка 2 Кучка 3
D + [000000] * C [100000] * C
Итак, мы добились следующего: в кучке 2 камней стало меньше, чем было изначально в кучке 3. То есть, минимальное количество во всех трех кучках уменьшилось.
Переобозначаем кучки, чтобы прийти к ситуации (Кучка1)A > (Кучка2)B > (Кучка3)C и повторяем алгоритм.
В итоге получим, что количество в кучке 2 = 0 (после каждого применения алгоритма оно уменьшается). То есть, на предыдущем шаге мы удвоили кучку 3 за счет кучки 2. А это и было «решение задачи».
 

Re: ОФФ Задачка для 6-го класса

iogri
172 - 16.03.2009 - 07:33
 блин, слетели табуляторы и стало нечитаемо :(
дублирую:
Имеем три кучки камней с количествами (Кучка1)A > (Кучка2)B > (Кучка3)C
Очевидно, что можно записать B = D + k*C (деление с остатком)
Алгоритм такой:
Представим k в двоичном виде (например [100101]). В квадратных скобках будем записывать двоичные числа
Тогда количество камней в кучках запишется так (количество в кучке 1 нас не интересует, важно, что там камней больше чем в кучке 2):
Кучка 1       Кучка 2                 Кучка 3
              D + [100101] * C        [1] * C
Если последний разряд в числе k = 1, то удваиваем кучку 3 за счет кучки 2:
Кучка 1       Кучка 2                 Кучка 3
              D + [100100] * C        [10] * C
Если пред-последний разряд в числе k = 0, то удваиваем кучку 3 за счет кучки 1:
Кучка 1       Кучка 2                 Кучка 3
              D + [100100] * C        [100] * C
Если пред-пред-последний разряд в числе k = 1, то удваиваем кучку 3 за счет кучки 2:
Кучка 1       Кучка 2                 Кучка 3
              D + [100000] * C        [1000] * C
И так далее…
В итоге, получим позицию:
Кучка 1       Кучка 2                 Кучка 3
              D + [000000] * C        [1000000] * C
Итак, мы добились следующего: в кучке 2 камней стало меньше, чем было изначально в кучке 3. То есть, минимальное количество во всех трех кучках уменьшилось.
Переобозначаем кучки, чтобы прийти к ситуации (Кучка1)A > (Кучка2)B > (Кучка3)C и повторяем алгоритм.
В итоге получим, что количество в кучке 2 = 0 (после каждого применения алгоритма оно уменьшается). То есть, на предыдущем шаге мы удвоили кучку 3 за счет кучки 2. А это и было «решение задачи».
 

Re: ОФФ Задачка для 6-го класса

roma n
173 - 16.03.2009 - 07:48
 "важно, что там камней больше чем в кучке 2" - загвоздка в том, что это утверждение после нескольких удваиваний (из кучки 3) может оказаться ложным и следующий шаг алгоритма невыполним

Re: ОФФ Задачка для 6-го класса

iogri
174 - 16.03.2009 - 08:05
 2(173)
На всех шагах алогритма (кроме последнего) "кучка 2" >= "кучки 3". "кучка 2" в ходе выполнения алгоритма не растет, значит в "кучку 3" будет добавлено камней не больше, чем было изначально в "кучке 2", а значит меньше, чем было в "кучке 1". На последнем шаге алогритма "кучка 3" удваивается за счет "кучки 2". Все нормально, камней хватает.

Re: ОФФ Задачка для 6-го класса

roma n
175 - 16.03.2009 - 08:26
 (174) в (173) мало-мало идейку недопонял :)
Стройненько.

Re: ОФФ Задачка для 6-го класса

Путевый лист
176 - 16.03.2009 - 09:13
 (Всем) Спасибо. Не оскудел Форум креативом и желанием разобраться,решить и добить задачу

Re: ОФФ Задачка для 6-го класса

КвазиСпец
177 - 16.03.2009 - 09:44
 Тема не раскрыта!
Никто не требовал найти алгоритм решения!
Требовалось всего-то доказать возможность уравнивания за конечное число ходов!

Re: ОФФ Задачка для 6-го класса

iogri
178 - 16.03.2009 - 10:20
 2(177)
Для доказательства возможности решения достаточно предложить алгоритм построения этого решения (сходящийся за конечное количество ходов).
Доказательства такого рода тоже применяются в математике.
Так что, задача решена.

Re: ОФФ Задачка для 6-го класса

Путевый лист
179 - 16.03.2009 - 10:53
 (Всем) Пока все-таки задачка не получила решения на уровне 6-го класса
И тем не менее похоже что алгоритм построения решения, предложенный iogri - ошибок не содержит и как-то можно попытаться обосновать его на уровне 6-го класса

Re: ОФФ Задачка для 6-го класса

roma n
180 - 21.04.2009 - 09:39
 179-Путевый лист >
Ответы так пока и не появились?
К списку тем 1 2 3 4 > К списку форумов

Добавить новое сообщение

Ваше имя:
Тема сообщения:
Сообщение:
« Если не вошел в форум - не видно разделов. Может правильно, а по-мне, так лучше-бы присоединить.. 1C и КПК »
© 2009 Форум 1С: Одинэс.Ру