Имя: Пароль:
IT
 
Пара задачек на чётность
,
0 Timon1405
 
08.06.15
10:40
Для одной темы каждая задачка маловата, поэтому сразу две)
1. Верно ли, что любое четное число можно представить в виде суммы двух натуральных чисел, все цифры которых нечетны?
2. Верно ли, что любое нечетное число, большее 1, можно представить в виде суммы трех натуральных чисел, все цифры которых нечетны?
1 Drac0
 
08.06.15
10:43
(0) 2 же следует из 1 моментально?
2 Timon1405
 
08.06.15
10:46
(1) Может следует, а может и не следует) Зависит от истинности 1.
3 Drac0
 
08.06.15
10:50
(0) Тогда тупо индукцией.

Для 2 - это 1 и 1,

для пусть на шаге к - это будет 2*к+1 = а1+а2, где а1 и а2 нечетные. Возьмем шаг к+1. ТОгда 2*(к+1)+1 = 2*к+1+2. Заменяем ,получаем а1+а2+2. (а2+2) - нечетное, т.к. а2 нечетное. Значит наше предположение верно. ЧИТД.
4 Drac0
 
08.06.15
10:51
(3) а потом уже (1)
5 SUA
 
08.06.15
10:52
(3)2*к+1 = а1+а2, где а1 и а2 нечетные это как?
6 Timon1405
 
08.06.15
10:53
(3) Нет, условие не до конца прочитал.
7 Drac0
 
08.06.15
10:54
(6) А, да. Точно. Тупанул. Еще подумал, что слишком уж просто :)
8 SUA
 
08.06.15
10:59
(0)1 - нет, пример 260
чтобы разложить по условиям задачи, максимальное число из суммы должно быть от 131 до 199, при этом соответствующее парное число будет иметь четную цифру в десятках
9 SUA
 
08.06.15
11:01
2 интереснее - но ушел работать
10 ILM
 
гуру
08.06.15
11:05
199 + 151 = 260
11 Бубка Гоп
 
08.06.15
11:06
(10) посчитай еще раз
12 toypaul
 
гуру
08.06.15
11:33
(8) в общем случае, если в числе есть 0, то разложить нельзя, если в следующем разряде у числа четное число. потому что 2 нечетных числа + 1 (от переноса получаемого от пред. 10) получается нечетное.
13 Timon1405
 
08.06.15
11:35
(12) 60=59+1
14 toypaul
 
гуру
08.06.15
11:37
(13) ну так не честно :) у 1 во втором разряде 0 :)
15 Timon1405
 
08.06.15
11:42
(14) 110=55+55)
16 toypaul
 
гуру
08.06.15
11:42
(0) по п.2

3 = 1 + 1 + 1
5 = 3 + 1 + 1

ну и так далее
17 toypaul
 
гуру
08.06.15
11:43
(15) у 110 десяток нечетный. а я писал, что если четный
18 Timon1405
 
08.06.15
11:43
(16) 23= 21+1+1?
19 toypaul
 
гуру
08.06.15
11:44
(18) ну да ...
20 Гёдза
 
08.06.15
11:45
0 - не натуральное число. Вопрос о его четности некорректен
21 Aceforg
 
08.06.15
11:48
(20) Хочешь сказать, что число 101 не содержит четных цифр?
22 toypaul
 
гуру
08.06.15
11:52
261 можно разложить как

131 + 119 + 11

то есть хотя 260 нельзя разложить на два числа с нечетными цифрами, 261 можно разложить скинув "лишние" единички к "базовой" 1.

в (18) также скидываем из 21 десяток к базовой 1 -
11 + 1 + 11
23 Гёдза
 
08.06.15
11:52
затупил. Четное, но не натуральное
24 Timon1405
 
08.06.15
11:54
(22) итого рассмотрены числа 3,5,23 и 261)
25 Timon1405
 
08.06.15
11:56
(22) "скиньте десяток" в 101=99+1+1
26 toypaul
 
гуру
08.06.15
11:57
(25) зачем?
27 Timon1405
 
08.06.15
11:59
(26) ошибочка не 101, а 301: 301=299+1+1 - не катит, по вашей логике должно прокатить 289+11+1
28 toypaul
 
гуру
08.06.15
12:01
(27) по моей логике это 199 + 1 + 101, затем 199 + 11 + 91
29 Timon1405
 
08.06.15
12:13
(28) теперь откуда-то взялось 101... пожалуйста, опишите поподробнее логику, вот берем число, что с ним делаем, и куда в каких случаях перекидываем какие единички. берем 431,
429+1+1 - не катит, 199+1+231 - тоже не катит, 199+11+221, что и куда нужно дальше перекинуть?
30 dervishsy
 
08.06.15
12:19
(0)ну если 0 исключить то любое четное число А можно представить как сумму (А-1) + 1.
31 Timon1405
 
08.06.15
12:23
(30) "ВСЕ цифры которых нечетны"
32 Asirius
 
08.06.15
17:51
(0) Нет в любых вариациях. Для любого конечного количества числел найдется число, которое нельзя разложить на сумму.
Потому что нечетных (четных) числел от 1 до 10^n будет 10^n/2,
а чисел с нечетными цифрами = 5+5^2+5^3+..+5^n
Т.е. можно взять достаточное большое n, чтобы первое множество нельзя было покрыть произведением вторых множеств
33 Timon1405
 
08.06.15
17:54
(32) Отсыпь и мне забористой)
34 Asirius
 
08.06.15
18:07
(32) А, не ошибся, (5^n)^3 > 10^n
35 SUA
 
08.06.15
19:17
ну и ответ на (0).2: да
431->311+61+59, в частности
- проверяем до 100 вручную
- выбираем первое число 111..11 (N1)
- конструируем (иногда прибавляя 2 к соответствующему разряду 1го числа) желаемый остаток (N-N1) по принципу:
- за нечетным - нечетное: выберем его из {1,5,9}
- за нечетным - четное: выберем его из {0,4,8}
- за четным - нечетное: выберем его из {3,7}
- за четным - четное: выберем его из {2,6}
И поделим остаток пополам (он будет состоять только из нечетных цифр)
36 SUA
 
08.06.15
19:17
не касаясь того что это можно сделать всегда
37 Casey1984
 
08.06.15
20:22
(0)

1. Верно ли, что любое четное число можно представить в виде суммы двух натуральных чисел, все цифры которых нечетны?

Ответ: Неверно.

Доказательство:

Натуральные числа (естественные числа) — числа, возникающие естественным образом при счёте. Множество натуральных чисел строго положительно, иногда к ним также причисляют 0.

Чётное число — целое число, которое делится на 2.
Нечётное число — целое число, которое не делится на 2 без остатка.

Чётные и нечетные числа принадлежат множеству целых чисел, которое заведомо больше множества натуральных числе, т.к. включает отрицательные числа.

Вывод:

Отрицательные четные числа нельзя представить в виде суммы натуральных нечетных чисел, так как если N > 0 и K > 0, то N + K > 0.
38 beaver1971
 
08.06.15
21:05
1.
Представим четное число в виде:
А = а(н)а(н-1)...а(3)а(2)а(1)
Первое нечетное слагаемое в виде:
Б = б(н)б(н-1)...б(3)б(2)б(1)
Второе нечетное слагаемое в виде:
В = в(н)в(н-1)...в(3)в(2)в(1)
для случая одноразрядных слагаемых верны следующие равенства:
б(1) + в(1) = а(1) либо б(1) + в(1) = 10 + а(1), то есть происходит перенос единицы в старший разряд.
В общем случае для четной суммы в самом младшем разряде всегда четная цифра. Подбираем пару нечетных цифр для слагаемых, которые дадут в результате либо а(м), либо 10 + а(м), если в следующем разряде суммы нечетная цифра.
Однако ноль может быть получен только в виде:
б(м) + в(м) = 10 + а(м), где а(м) = 0, то есть всегда возникает перенос единицы в старший разряд.
Тогда, если сумма представлена в виде ...а(м+3)а(м+2)а(м+1)..., где а(м+1) = 0, а(м+2) и а(м+3) - любые четные цифры, то какую бы пару б(м+1) и в(м+1) мы не подобрали, а(м+2) должна быть равна б(м+2) + в(м+2) + 1. Это возможно, только если б(м+2) (или в(м+2)) равны нулю, то есть разрядность числа б (или в) ограничена м+2 позициями, но тогда для получения четной а(м+3) нет ни какой возможности, ибо в(м+3) + 0 всегда будет нечетное число.
Ответ: невозможно
39 RomanYS
 
08.06.15
21:34
вторая задача. При любой цифре в последнем разряде у нас есть возможность отнять от следующего разряда четное или нечетное число
для последней 1 можно отнять 11 или 21; для 3: 3, 13, 23; для 5: 5, 15, 25; для 7: 7, 17, 27; для 9: 9, 19.
В итоге мы всегда можем так избавиться от младшего разряда так, чтобы оставшееся число было нечетным. Повторяем до последнего разряда. Ответ: возможно (если не учитывать (37) - не поспоришь)

для первой задачи такой фокус не проходит: при нуле в последнем разряде, при избавлении от младшего разряда в любом случае от числа отнимем 10. Получившееся число (отняли 10, отбросили 0) может оказаться нечетным. Для чисел меньше 200 спасает возможность иметь 0 в старшем разряде (разная разрядность чисел). Начиная с 220 разложить уже не получится.
40 TawnyOwl
 
08.06.15
21:35
По 1, можно без сложных размышлений написать простенький скрипт, который полным перебором найдет нам 220, которое нельзя разложить на слагаемые из нечетных цифр. Убедиться что нельзя можно с помощью excel, там всего-то 55 пар надо глазами проверить.
41 Casey1984
 
08.06.15
21:38
(40) Любое отрицательное четное уже не подходит. И никаких сложных размышлений)
42 hhhh
 
08.06.15
21:43
(39) а какой смысл отнимать 21?
43 RomanYS
 
08.06.15
21:48
(42) нужно чтобы при отбрасывании младшего разряда осталось нечетное число.
Например, от 411 отнимаем 21, чтобы получить 39; а от 421 отнимаем 11, чтобы получить 41
44 hhhh
 
08.06.15
21:51
(43) но в 21 ведь четная цифра. Оно не подходит.
45 RomanYS
 
08.06.15
21:56
(44) 21 = 7+7+7 = 5+7+9 = 3+9+9 эти цифры будут в последнем разряде разложения, а "2" отнимаем от следующего разряда
46 Casey1984
 
08.06.15
23:55
Зачем смотреть на старшие разряды, если нужен только младший из определения нечетного числа и признаков делимости на два)

Для нечетных:
...1 = 1 + 1 + 9
...3 = 1 + 1 + 1
...5 = 1 + 1 + 3
...7 = 1 + 1 + 5
...9 = 1 + 1 + 7

А остальные разряды какие угодно, вплоть до "все нечетные".
47 SUA
 
10.06.15
14:40
(39)как по такой логике разложить 1111?
(41)четное натуральное больше устроит?
48 RomanYS
 
10.06.15
14:48
(47)
1111
1)  могу отнять 11(останется 110*10) или 21 (отстанется 109*10). Устраивает 109, т.к. нечетное
21=7+7+7

2)109: отнимаем 9 (ост. 10*10) или 19 (9*10)
выбираем остаток 9
19 = 7+7+5

3)9 = 3+3+3

Итого 1111=377+377+357
49 Timon1405
 
10.06.15
15:12
Логика у всех решивших примерно одинаковая, привожу авторское решение.
Заметим, что получить последнюю нечетную цифру нужной суммы можно, используя последние цифры трех слагаемых двумя способами, в одном из которых перенос в следующий разряд четное число, а в другом – нечетное (…1 = 7 + 3 + 1 = 7 + 7 + 7, 3 = 7 + 1 +5 = 7 + 7 + 9 и т.д.) Таким образом, можно построить слагаемые, начиная с младших разрядов, подбирая их цифры, чтобы получать цифры суммы и четный перенос в следующий разряд, кроме самого последнего переноса, который обеспечит нечетность последнего разряда суммы.