Математический форум 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/ |