Математический форум Math Help Planet
http://mathhelpplanet.com/

Сумма 5x + 3y
http://mathhelpplanet.com/viewtopic.php?f=10&t=59705
Страница 1 из 1

Автор:  Mahler [ 08 май 2018, 00:33 ]
Заголовок сообщения:  Сумма 5x + 3y

Добрый день!
Решал задачку по программированию, которая оказалась с подвохом, вот условия:
В кафе мороженое продают по три шарика и по пять шариков. Можно ли купить ровно k шариков мороженого?
Решение задачи -- все натуральные числа, кроме 1, 2, 4 и 7.

Математический бэкграунд у меня стремится к нулю, но меня заинтересовало, как можно строго выразить и доказать, что сумма решений покрывает все множество натуральных чисел, кроме указанных?
Буду рад помощи и советам, что почитать на этот счет.
Спасибо!

Автор:  Booker48 [ 08 май 2018, 00:43 ]
Заголовок сообщения:  Re: Сумма 5x + 3y

Рассмотрим остаток от деления числа [math]k[/math] на [math]3[/math]. Если он равен [math]0[/math], то задача решена (просто покупаем [math]\frac{k}{3}[/math] порций по [math]3[/math] шарика). Если он равен [math]2[/math], то [math]k-5[/math] делится на [math]3[/math] без остатка. Т.е. покупаем одну порцию из [math]5[/math] шариков и [math]\frac{k-5}{3}[/math] порций по [math]3[/math] шарика. Если он равен [math]1[/math], то...

Автор:  Pavel_Kotoff [ 08 май 2018, 01:00 ]
Заголовок сообщения:  Re: Сумма 5x + 3y

Диофантово уравнение? Похоже...

Автор:  Mahler [ 08 май 2018, 01:36 ]
Заголовок сообщения:  Re: Сумма 5x + 3y

Booker48 писал(а):
Mahler писал(а):
Если он равен [math]1[/math], то...


Начинается самое интересное! Я не смог найти какую-то формулу, но заметил закономерность, в суммах цифр чисел, у которых остаток от деления k/3 составляет 1. Это те самые 1, 4 и 7, которые не входят в область решения.
То есть:
13 -> 1+3 ->4
16 -> 1+6 ->7
19 -> 1+9 > 1
22 -> 2+2 ->4
28 -> 2+8 -> 1
31 -> 3+1 -> 4
34 - > 3+4 -> 7
37 - > 3+7 -> 1

Но это не помогает)

Автор:  FEBUS [ 08 май 2018, 01:50 ]
Заголовок сообщения:  Re: Сумма 5x + 3y

Mahler писал(а):
Но это не помогает
Что не понятно?
[math]k = 3n[/math]
[math]k = 3n + 1 = 3(n - 3) + 10[/math]
[math]k = 3n - 1 = 3(n - 2) + 5[/math]

Автор:  Slon [ 08 май 2018, 13:45 ]
Заголовок сообщения:  Re: Сумма 5x + 3y

Эта задача очень старая и детская, детям ее объясняют так:
вот от 8 до 10 можно сделать - можно, а потом добавляем по 3 значит от 11 до 13 тоже можно и т.д.
Короче нужно понять, что если три последовательных числа получились, то все после них тоже получатся

Автор:  3D Homer [ 08 май 2018, 17:08 ]
Заголовок сообщения:  Re: Сумма 5x + 3y

Добавлю, что множество [math]\{3x+5y\mid x,y=0,1,2,\dots\}[/math] является числовой полугруппой с порождающими 3 и 5. Дополнение к числовой полугруппе конечно. Максимальное число, не входящее в полугруппу, называется числом Фробениуса. Оно равно [math](a-1)(b-1)-1[/math] в случае двух порождающих [math]a[/math] и [math]b[/math] (в данном случае (3-1)(5-1)-1 = 7). Мощность дополнения к полугруппе в случае двух образующих есть [math](a-1)(b-1) \slash 2[/math] (в данном случае (3-1)(5-1)/2 = 4).

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/