Реально сложная задачка
vk f t

Реально сложная задачка

Логи­ка, мате­ма­ти­ка и анти­со­ци­аль­ное пове­де­ние.

Помни­те двух про­грам­ми­стов и их диа­лог про воз­раст сыно­вей? Они встре­ти­лись сно­ва! Вот их исто­рия.

Дво­их про­грам­ми­стов вывез­ли на клад­би­ще бан­ди­ты из девя­но­стых. Бан­ди­ты тай­но выбра­ли 2 целых поло­жи­тель­ных чис­ла, оба боль­ше еди­ни­цы, а их сум­ма мень­ше 100. Пер­во­му про­грам­ми­сту бан­дит ска­зал про­из­ве­де­ние этих чисел, а вто­ро­му — их сум­му. После это­го у про­грам­ми­стов состо­ял­ся такой раз­го­вор.

Пер­вый: Я поня­тия не имею, какая у тебя сум­ма.
Вто­рой: Ха-ха, это для меня не новость! Я и так знал, что ты не знал это­го.
Пер­вый: Ага! Теперь я понял, чему рав­на твоя сум­ма!
Вто­рой: Отлич­но — теперь и я тоже знаю твоё про­из­ве­де­ние!

Бан­ди­ты, конеч­но же, их отпу­сти­ли. Пото­му что это загад­ка! А загад­ка в том, что это за чис­ла и как про­грам­ми­сты это выяс­ни­ли.

Реше­ние

В отли­чие от преды­ду­щей зада­чи, здесь реше­ние намно­го слож­нее, пото­му что в голо­ве нуж­но дер­жать одно­вре­мен­но 2-3 усло­вия, кото­ры­ми надо про­ве­рять чис­ла. Но мы спра­вим­ся.

Для реше­ния нам пона­до­бит­ся вспом­нить, что такое про­стые чис­ла и в чём их осо­бен­ность. Про­стое чис­ло — то, кото­рое может делить­ся наце­ло толь­ко на себя и на еди­ни­цу. Напри­мер, чис­ло 5 — про­стое, пото­му что делит­ся толь­ко на 5 и на 1. А чис­ло 6 — не про­стое, пото­му что кро­ме 6 и 1 оно ещё делит­ся на 2 и 3 без остат­ка. Семь тоже будет про­стым чис­лом, а восемь — нет, пото­му что кро­ме 8 и 1 оно делит­ся так­же на 2 и 4.

Если пере­мно­жить два про­стых чис­ла, то полу­чен­ное про­из­ве­де­ние боль­ше никак нель­зя полу­чить дру­гим спо­со­бом (кро­ме умно­же­ния это­го же чис­ла на еди­ни­цу). Пояс­ним на при­ме­ре.

Возь­мём два про­стых чис­ла 5 и 7 и пере­мно­жим их — полу­чит­ся 35. Боль­ше чис­ло 35 полу­чить никак не полу­чит­ся, кро­ме как умно­жить 35 на 1. Это зна­чит, что если про­из­ве­де­ние мож­но раз­ло­жить на два про­стых мно­жи­те­ля, то дру­гих вари­ан­тов раз­ло­же­ния (кро­ме чис­ла и еди­ни­цы) у него не будет. Это нам при­го­дит­ся при реше­нии задач — и если чис­ло мож­но раз­ло­жить на 2 про­стых, то и их сум­му тоже лег­ко сра­зу посчи­тать.

Ещё при­мер:

54 = 2 × 27

54 = 3 × 18

54 = 6 × 9, а это зна­чит, что чис­ло 54 нель­зя полу­чить пере­мно­же­ни­ем двух про­стых чисел и нель­зя сра­зу ска­зать, чему одно­знач­но рав­на сум­ма мно­жи­те­лей.

И ещё:

21 = 3 × 7

Оба чис­ла про­стые, поэто­му про­из­ве­де­ние 21 мож­но полу­чить толь­ко из них, а зна­чит, лег­ко посчи­тать сум­му — она будет рав­на 3 + 7 = 10.

Теперь пере­ве­дём их диа­лог на язык мате­ма­ти­ки и логи­ки и обо­зна­чим чис­ла как n и m:

Пер­вый: Я понял, что одно из чисел точ­но не про­стое, пото­му что ина­че я сра­зу бы раз­ло­жил чис­ло на про­из­ве­де­ние двух про­стых и лег­ко полу­чил сум­му. А раз так, то это одно из чисел m или n мож­но полу­чить пере­мно­же­ни­ем двух дру­гих чисел. Поэто­му общее про­из­ве­де­ние состо­ит не менее чем из трёх мно­жи­те­лей, при­чём как мини­мум один из них отли­ча­ет­ся от осталь­ных — поэто­му полу­ча­ет­ся несколь­ко вари­ан­тов воз­мож­ных сумм, и я не знаю, какая из них пра­виль­ная (поме­тим это как Пра­ви­ло 1).

Вто­рой: Сум­му, кото­рая у меня есть, нель­зя полу­чить из двух про­стых чисел, поэто­му и твоё про­из­ве­де­ние тоже нель­зя раз­ло­жить на два про­стых мно­жи­те­ля. Это зна­чит, что у меня нечёт­ная сум­ма, пото­му что, по гипо­те­зе Гольд­ба­ха, в нашем слу­чае мож­но полу­чить любое чёт­ное чис­ло, сло­жив два про­стых. А раз это не два про­стых чис­ла, зна­чит, и сум­ма будет нечёт­ная. А ещё эта сум­ма точ­но не рав­на сум­ме двух и про­сто­го чис­ла, пото­му что два — тоже про­стое, ха! Поэто­му есть несколь­ко вари­ан­тов сум­мы m и n, кото­рые под­хо­дят под твои усло­вия, но я не могу пока опре­де­лить, какие имен­но (поме­тим это как Пра­ви­ло 2).

Пер­вый: Из всех мно­жи­те­лей мое­го про­из­ве­де­ния я могу соста­вить толь­ко один вари­ант пары, сум­ма кото­рой подой­дёт под твоё огра­ни­че­ние — не будет раз­би­вать­ся на сум­му двух про­стых или сум­му чисел одно­го мно­жи­те­ля (Пра­ви­ло 3).

Вто­рой: Ах вот как! Из всех вари­ан­тов пар, на кото­рые мож­но раз­бить сум­му и под­хо­дя­щих под твои усло­вия, есть толь­ко одна, кото­рая поз­во­ли­ла бы тебе опре­де­лить это (Пра­ви­ло 4). Теперь и мне понят­но, что это за чис­ла!

Теперь под­бе­рём вари­ан­ты сум­мы, кото­рая была у вто­ро­го. Огра­ни­че­ния такие:

  • нечёт­ная;
  • не рав­на сум­ме двой­ки и про­сто­го чис­ла.

1 — не под­хо­дит, пото­му что оба чис­ла боль­ше еди­ни­цы.

2, 4, 6, 8… — нет, пото­му что чёт­ные.

3 — нет, пото­му что это сум­ма двой­ки и про­сто­го чис­ла.

5 — нет, по той же при­чине (2 + 3).

7 — тоже нет (2 + 5).

9 — тоже нет (2 + 7, а 7 — про­стое чис­ло).

11 — под­хо­дит.

13 — нет, пото­му что 13 = 2 + 11 (11 — про­стое чис­ло).

15 — нет, пото­му что 15 = 2 + 13 (13 — тоже про­стое чис­ло).

17 — под­хо­дит.

19 — нет, пото­му что 19 = 2 + 17 (17 — про­стое чис­ло).

Спо­соб под­бо­ра сум­мы поня­тен, даль­ше мож­но про­дол­жать по тому же алго­рит­му. Мы же выбе­рем те, кото­рые нам уже подо­шли, и на их при­ме­ре пока­жем, что нуж­но делать даль­ше, что­бы полу­чить пра­виль­ный ответ. Наши чис­ла, кото­рые нам под­хо­дят уже сей­час: 11 и 17. Нач­нём с 11.

Сум­ма = 11.

Най­дём все сла­га­е­мые, кото­рые могут давать эту сум­му:

2 + 9

3 + 8

4 + 7

5 + 6

Для каж­до­го из них запи­шем про­из­ве­де­ние и про­ве­рим, выпол­ня­ет­ся ли Пра­ви­ло 3, кото­рое ска­зал пер­вый про­грам­мист.

Смот­рим на про­из­ве­де­ние 2 × 9 = 18 и как ещё его мож­но полу­чить.

18 = 2 × 9 → Да (Пра­ви­ло 3 выпол­ня­ет­ся).

18 = 3 × 6 → Нет (Пра­ви­ло 3 не рабо­та­ет, пото­му что 3 + 6 = 9, а 9 мож­но полу­чить из про­стых чисел 2 и 7).

Смот­рим на про­из­ве­де­ние 3 × 8 = 24.

24 = 2 × 12 → Нет (чёт­ная сум­ма, Пра­ви­ло 2 не рабо­та­ет).

24 = 3 × 8 → Да (выпол­ня­ет­ся Пра­ви­ло 3).

24 = 6 × 4 → Нет (чёт­ная сум­ма).

Смот­рим на про­из­ве­де­ние 4 × 7 = 28.

28 = 2 × 14 → Нет (чёт­ная сум­ма).

28 = 4 × 7 → Да (выпол­ня­ет­ся Пра­ви­ло 3).

Смот­рим на про­из­ве­де­ние 5 × 6 = 30.

30 = 2 × 15 → Да.

30 = 3 × 10 → Нет (Пра­ви­ло 3 не рабо­та­ет, пото­му что 3 + 10 = 13, а 13 мож­но полу­чить сум­мой про­стых чисел 2 и 11).

30 = 5 × 6 → Да.

Тут мы вооб­ще не можем выбрать одну пару, пото­му что Пра­ви­ло 3 выпол­ня­ет­ся 2 раза, а зна­чит, этот вари­ант отбра­сы­ва­ем.

Полу­ча­ет­ся, что для сум­мы 11 могут быть три вари­ан­та про­из­ве­де­ний, для кото­рых выпол­ня­ет­ся Пра­ви­ло 3: 2 и 9, 3 и 8, 4 и 7. Но тогда Пра­ви­ло 4 не выпол­ня­ет­ся, пото­му что нуж­но, что­бы для одной сум­мы была толь­ко одна пара, кото­рая под­хо­дит под пра­ви­ло 3. Про­дол­жа­ем искать.

Сум­ма = 17.

Най­дём все сла­га­е­мые, кото­рые могут давать эту сум­му:

2 + 15

3 + 14

4 + 13

5 + 12

6 + 11

7 + 10

8 + 9

Для каж­до­го из них запи­шем про­из­ве­де­ние и про­ве­рим, выпол­ня­ет­ся ли Пра­ви­ло 3, кото­рое ска­зал пер­вый про­грам­мист.

Смот­рим на про­из­ве­де­ние 2 × 15 = 30 и как ещё его мож­но полу­чить.

30 = 2 × 15 → Да.

30 = 3 × 10 → Нет (Пра­ви­ло 3 не рабо­та­ет, пото­му что 3 + 10 = 13, а 13 мож­но полу­чить сум­мой про­стых чисел 2 и 11).

30 = 5 × 6 → Да.

Тут мы вооб­ще не можем выбрать одну пару, пото­му что Пра­ви­ло 3 выпол­ня­ет­ся 2 раза, а зна­чит, этот вари­ант отбра­сы­ва­ем.

Смот­рим на про­из­ве­де­ние 3 × 14 = 42 и как ещё его мож­но полу­чить:

42 = 2 × 21 → Да.

42 = 3 × 14 → Да.

42 = 6 × 7 → Нет.

Два раза выпол­ня­ет­ся Пра­ви­ло 3 — отбра­сы­ва­ем пару.

Смот­рим на про­из­ве­де­ние 4 × 13 = 52 и как ещё его мож­но полу­чить.

52 = 2 × 26 → Нет.

52 = 4 × 13 → Да.

Смот­рим на про­из­ве­де­ние 5 × 12 = 60 и как ещё его мож­но полу­чить.

60 = 2 × 30 → Нет.

60 = 3 × 20 → Да.

60 = 5 × 12 → Да.

60 = 6 × 10 → Нет.

Два раза выпол­ня­ет­ся Пра­ви­ло 3 — отбра­сы­ва­ем пару.

Смот­рим на про­из­ве­де­ние 6 × 11 = 66 и как ещё его мож­но полу­чить.

66 = 2 × 33 → Да.

66 = 3 × 22 → Нет.

66 = 6 × 11 → Да.

Два раза выпол­ня­ет­ся Пра­ви­ло 3 — отбра­сы­ва­ем пару.

Смот­рим на про­из­ве­де­ние 7 × 10 = 70 и как ещё его мож­но полу­чить.

70 = 2 × 35 → Да.

70 = 5 × 14 → Нет.

70 = 7 × 10 → Да.

Два раза выпол­ня­ет­ся Пра­ви­ло 3 — отбра­сы­ва­ем пару.

Смот­рим на про­из­ве­де­ние 8 × 9 = 72 и как ещё его мож­но полу­чить.

72 = 2 × 36 → Нет.

72 = 3 × 24 → Да.

72 = 4 × 18 → Нет.

72 = 6 × 12 → Нет.

72 = 8 × 9 → Да.

Два раза выпол­ня­ет­ся Пра­ви­ло 3 — отбра­сы­ва­ем пару.

Полу­ча­ет­ся, что для сум­мы 17 может быть толь­ко один вари­ант про­из­ве­де­ния, для кото­ро­го выпол­ня­ет­ся Пра­ви­ло 3: это 4 и 13. А зна­чит, что Пра­ви­ло 4 тоже выпол­ня­ет­ся и мы нашли нуж­ные чис­ла!

Если вы дочи­та­ли досю­да и всё поня­ли — сни­ма­ем шля­пу. Вы не из тех, кого могут испу­гать вычис­ле­ния и логи­че­ский под­ход!

Ещё по теме