В 15-литровые ведра налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть. Какое наибольшее количество воды можно
собрать в одном ведре?

Здравствуйте, nikholas, Вы писали:

N>В 15-литровые ведра налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть. Какое наибольшее количество воды можно
N>собрать в одном ведре?

2+4
6+3
вывод: 9

Здравствуйте, nikholas, Вы писали:

N>В 15-литровые ведра налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть. Какое наибольшее количество воды можно
N>собрать в одном ведре?

Что мешает собрать 15?

1 -> 3
2 -> 4
и их содержимое слить в 5

Здравствуйте, dimok@, Вы писали:

D>Здравствуйте, nikholas, Вы писали:

N>>В 15-литровые ведра налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть. Какое наибольшее количество воды можно
N>>собрать в одном ведре?

D>Что мешает собрать 15?

D>1 -> 3
D>2 -> 4
D>и их содержимое слить в 5
Тогда сразу 80 можно сделать. Правда в других ведрах будут отрицательные значения

Здравствуйте, denisko, Вы писали:

D>Тогда сразу 80 можно сделать. Правда в других ведрах будут отрицательные значения

Сарказм? Какое условие нарушено?

Здравствуйте, dimok@, Вы писали:

D>Здравствуйте, denisko, Вы писали:

D>>Тогда сразу 80 можно сделать. Правда в других ведрах будут отрицательные значения

D>Сарказм? Какое условие нарушено?
9 < 10

Здравствуйте, denisko, Вы писали:

D>9 < 10

нет такого условия и 9-ти тоже нет

есть 3+1=4 и 4+2=6

Здравствуйте, nikholas, Вы писали:

N>В 15-литровые ведра налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть. Какое наибольшее количество воды можно
N>собрать в одном ведре?

0)
1 — 1
2 — 2
3 — 3
4 — 4
5 — 5

2 -> 1
1)
1 — 3
2 — 0
3 — 3
4 — 4
5 — 5

4 -> 1
2)
1 — 7
2 — 0
3 — 3
4 — 0
5 — 5

5 -> 3
3)
1 — 7
2 — 0
3 — 8
4 — 0
5 — 0

3 -> 1
4)
1 — 15
2 — 0
3 — 0
4 — 0
5 — 0

Ответ 15 литров

Здравствуйте, nikholas, Вы писали:

N> Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть.
Как же криво сформулировано это условие
Решил исходить из формулировки, что

Если в паре вёдер u и v литров воды, то после переливания в них будет 3u и (v-2u) литров соответственно. При этом 3u ≤ 15, а (v-2u) ≥ 0, иначе переливание недопустимо. Другие способы переливания недопустимы.

N>Какое наибольшее количество воды можно собрать в одном ведре?
12, если так сливать:

1  2  3  4  5
   |        |
   | ------/ 
   |/
1  6  3  4  1
   |  |
    \ |
     \|
1  0  9  4  1
      |  |
       \ |
        \|
1  0  1  12 1

Здравствуйте, dimok@, Вы писали:

D>Здравствуйте, denisko, Вы писали:

D>>9 < 10

D>нет такого условия и 9-ти тоже нет

D>есть 3+1=4 и 4+2=6

я так понимаю, что загвоздка в том, что можно НАЛИТЬ В ведро а не ПЕРЕЛИТЬ ИЗ, как в предложенном условии

Здравствуйте, watchmaker, Вы писали:


W>12, если так сливать:

Осталось доказать, что больше нельзя

Здравствуйте, nikholas, Вы писали:

N>Осталось доказать, что больше нельзя

Что там доказывать-то? Всё очевидно:

Здравствуйте, nikholas, Вы писали:

N>В 15-литровые ведра налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть. Какое наибольшее количество воды можно
N>собрать в одном ведре?

Полным перебором решается:

первый шаг
1 2 3 4 5
\_/         3 0 3 4 5  =  0 3 3 4 5
\___/       3 2 1 4 5  =  1 2 3 4 5  - повтор (больше не будем переливать из 3 в 1, а также из 6 в 2 и из 9 в 3)
\_____/     3 2 3 2 5  =  2 2 3 3 5
\_______/   3 2 3 4 3  =  2 3 3 3 4
  \___/     1 6 3 0 5  =  0 1 3 5 6
  \_____/   1 6 3 4 1  =  1 1 3 4 6

итого
0 1 3 5 6
0 3 3 4 5 - тупик (нет пар с разницей не менее, чем в 2 раза)
1 1 3 4 6
2 2 3 3 5
2 3 3 3 4

второй шаг
0 1 3 5 6
  \___/    0 3 3 3 6  =  0 3 3 3 6
  \_____/  0 3 3 5 4  =  0 3 3 4 5
    \___/  0 1 9 5 0  =  0 0 1 5 9
1 1 3 4 6
  \___/    1 3 3 2 6  =  1 2 3 3 6
  \_____/  1 3 3 4 4  =  1 3 3 4 4
    \____/ 1 1 9 4 0  =  0 1 1 4 9
2 2 3 3 5
  \_____/  2 6 3 3 1  =  1 2 3 3 6
2 3 3 3 4
\_______/  6 3 3 3 0  =  0 3 3 3 6

итого, новые векторы
0 0 1 5 9
0 1 1 4 9
0 3 3 3 6
1 2 3 3 6
1 3 3 4 4

третий шаг
0 0 1 5 9
    \_/    0 0 3 3 9  =  0 0 3 3 9
    \___/  0 0 3 5 7  =  0 0 3 5 7
0 1 1 4 9
    \_/    0 1 3 2 9  =  0 1 2 3 9
    \___/  0 1 3 4 7  =  0 1 3 4 7
      \_/  0 1 1 12 1 =  0 1 1 1 12
0 3 3 3 6
      \_/  0 3 3 9 0  =  0 0 3 3 9
1 2 3 3 6
\_/        3 0 3 3 6  =  0 3 3 3 6
\_______/  3 2 3 3 4  =  2 3 3 3 4
      \_/  1 2 3 9 0  =  0 1 2 3 9
1 3 3 4 4
\_____/    3 3 3 2 4  =  2 3 3 3 4

итого
0 0 3 3 9  - тупик (есть только изоморфная пара 3-9)
0 0 3 5 7
0 1 1 1 12
0 1 2 3 9
0 1 3 4 7

четвёртый шаг
0 0 3 5 7
0 1 1 1 12
0 1 2 3 9
0 1 3 4 7

пятый шаг
0 1 1 3 10
0 2 3 3 7

шестой шаг
0 1 3 3 8

Итого, 12

А поскольку это этюд для программистов, то — код на питоне

# -*- coding : utf-8 -*-

def perelit_g(v) :
    ''' переливает из элементов кортежа (упорядоченного), порождая новые кортежи '''
    n = len(v)
    for i in range(0,n) :
        if v[i] > 0 :
            for j in range(i+1,n) :
                if v[i]*2 <= v[j] :
                    w = list(v)
                    w[i], w[j] = v[i] + v[i]*2, v[j] - v[i]*2
                    yield tuple(sorted(w))


def perelit(v) :
    ''' множество порождённых кортежей '''
    return set(perelit_g(v))

def perelits(vv) :
    ''' для множества исходных кортежей - множество порождённых '''
    ww = map(perelit, vv) # список множеств кортежей
    uu = reduce(lambda x,y:x|y, ww, set()) # объединённое множество кортежей
    return uu


v0 = (1,2,3,4,5) # стартовый кортеж

vv = {v0}  # множество кортежей, из которых будем порождать новые
vvall = vv # множество всех встреченных кортежей
while vv : # пока есть из чего порождать
    vv = perelits(vv)
    vv -= vvall # вычтем ранее встреченные
    vvall |= vv # запомним новые
    print '-----------'
    for s in sorted(vv) :
        print ' '.join(map(str,s))

print '==========='
for s in sorted(vvall) :
    print ' '.join(map(str,s))
print '==========='

m = max(max(s) for s in vvall)
print 'maximum maximorum =', m

Здравствуйте, nikholas, Вы писали:

N>В 15-литровые ведра налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть. Какое наибольшее количество воды можно
N>собрать в одном ведре?
У меня получилось 14.
1. 5-ое переливаем в 4-ое -> 1, 2, 3, 8, 1
2. 3-е в 1-ое -> 2, 2, 2, 8, 1
3. 4-ое в 5-ое -> 2, 2, 2, 7, 2
4. 1-ое во 2-ое -> 0, 4, 2, 7, 2
5. 5-ое в 3-е -> 0, 4, 4, 7, 0
6. 2-ое в 3-е -> 0, 0, 8, 7, 0
7. 3-е в 4-ое -> 0, 0, 1, 14, 0

Здравствуйте, debugx, Вы писали:

D>Здравствуйте, nikholas, Вы писали:

N>>В 15-литровые ведра налито соответственно 1, 2, 3, 4 и 5 литров воды. Разрешается перелить из любого ведра в любое другое вдвое больше воды, чем в нем уже есть. Какое наибольшее количество воды можно
N>>собрать в одном ведре?
D>У меня получилось 14.
D>1. 5-ое переливаем в 4-ое -> 1, 2, 3, 8, 1
D>2. 3-е в 1-ое -> 2, 2, 2, 8, 1
D>3. 4-ое в 5-ое -> 2, 2, 2, 7, 2
D>4. 1-ое во 2-ое -> 0, 4, 2, 7, 2
D>5. 5-ое в 3-е -> 0, 4, 4, 7, 0
D>6. 2-ое в 3-е -> 0, 0, 8, 7, 0
D>7. 3-е в 4-ое -> 0, 0, 1, 14, 0

Разрешается перелить из любого ведра в любое другое вдвое больше воды

Здравствуйте, Vaako, Вы писали:

V>Разрешается перелить из любого ведра в любое другое вдвое больше воды

А вы решение прочитали? Там вроде все четко. Идея в том, что 7ка достижима за счет того, что мы выливаем из 8 в 1, так как имеем право удвоить 1. Ну а потом осталось удвоить 7ку. 15ка понятно почему не получится — это не удвоение.

N>Здравствуйте, Vaako, Вы писали:

V>>Разрешается перелить из любого ведра в любое другое вдвое больше воды

N>А вы решение прочитали? Там вроде все четко.
Там же решение другой задачи.

N> это не удвоение.

Удвоение — это когда переливается ровно столько воды сколько уже есть в целевом ведре.
А когда переливается в ведро вдвое больше воды — это утроение, а не удвоение.

W>Удвоение — это когда переливается ровно столько воды сколько уже есть в целевом ведре.
W>А когда переливается в ведро вдвое больше воды — это утроение, а не удвоение.
И где же в том решении неправильный шаг?

Здравствуйте, Nuseraro, Вы писали:

W>>Удвоение — это когда переливается ровно столько воды сколько уже есть в целевом ведре.
W>>А когда переливается в ведро вдвое больше воды — это утроение, а не удвоение.
N>И где же в том решении неправильный шаг?
В том решении

Автор: debugx
Дата: 21.08.14

каждый шаг неправильный :)
Ведь после каждого шага происходит удвоение объёма в каком-либо ведре, хотя разрешено лишь утраивать его. Это как с процентами — рост на 200% означает увеличение в три раза, а не в два. Так и тут, если перелили в ведро вдвое больше воды чем там уже было, то в нем окажется втрое больше воды чем до переливания.

Здравствуйте, watchmaker, Вы писали:

N>>Какое наибольшее количество воды можно собрать в одном ведре?
W>12, если так сливать:

W>1  2  3  4  5
W>   |        |
W>   | ------/ 
W>   |/
W>1  6  3  4  1
W>   |  |
W>    \ |
W>     \|
W>1  0  9  4  1
W>      |  |
W>       \ |
W>        \|
W>1  0  1  12 1
W>

Остается открытым вопрос как из 9-литрового ведра вылить 8 литров в 4-х литровое. В задачах с ведрами обычно этот вопрос важен