2018 като сбор от квадрати

[pal702004]

Представете числото $2018$ като сбор на възможно най-много различни квадрати на естествени числа.

(Задачата е от олимпиада няма да кажа от коя година).

[Евва]

[tex]2^{2 }+ 4^{2 }+ 5^{2 }+ 6^{2 } + 7^{2 }+ 8^{2 } + 10^{2 } + 11^{2 } + 12^{2 } + 13^{2 } + 14^{2 } + 15^{2 } + 16^{2 } + 17^{2 }+ 18^{2 }[/tex] =2 018

[pal702004]

Евва, $15$ е добре, но може и по-добре.

[Евва]

Подскажете ми- освен метода на налучкването какъв друг метод мога да използвам ?

[peyo]

Тоа е забавна задача!

Код: Избери целия код

from functools import lru_cache
import math

maxlen = 0

@lru_cache(maxsize=None)
def search(s):
   global maxlen
   if sum(s) == 2018 and maxlen < len(s):
      maxlen = len(s)
      nums = [math.sqrt(a) for a in s]
      print(maxlen, "$\Rightarrow", ", ".join([ "%d^2 "%a for a in nums]), "$")
      return
   if sum(s)<2018:
      return
   for i in range(len(s)):
      sc = list(s[:])
      del sc[i]
      search( tuple(sc))

squares = tuple([ a**2 for a in range(1,21)])
search(squares)

10 $\Rightarrow 7^2 , 8^2 , 11^2 , 12^2 , 13^2 , 14^2 , 15^2 , 17^2 , 19^2 , 20^2 $
11 $\Rightarrow 7^2 , 8^2 , 9^2 , 10^2 , 11^2 , 13^2 , 14^2 , 15^2 , 17^2 , 18^2 , 20^2 $
12 $\Rightarrow 7^2 , 8^2 , 9^2 , 10^2 , 11^2 , 12^2 , 13^2 , 14^2 , 15^2 , 16^2 , 17^2 , 18^2 $
13 $\Rightarrow 4^2 , 6^2 , 7^2 , 8^2 , 9^2 , 10^2 , 11^2 , 12^2 , 13^2 , 15^2 , 17^2 , 18^2 , 20^2 $
14 $\Rightarrow 4^2 , 5^2 , 6^2 , 7^2 , 8^2 , 9^2 , 10^2 , 11^2 , 12^2 , 13^2 , 14^2 , 16^2 , 19^2 , 20^2 $
15 $\Rightarrow 2^2 , 4^2 , 5^2 , 6^2 , 7^2 , 8^2 , 10^2 , 11^2 , 12^2 , 13^2 , 14^2 , 15^2 , 16^2 , 17^2 , 18^2 $
16 $\Rightarrow 1^2 , 2^2 , 3^2 , 4^2 , 5^2 , 6^2 , 7^2 , 8^2 , 10^2 , 12^2 , 13^2 , 14^2 , 15^2 , 16^2 , 18^2 , 20^2 $
17 $\Rightarrow 1^2 , 2^2 , 3^2 , 4^2 , 5^2 , 6^2 , 7^2 , 8^2 , 9^2 , 10^2 , 11^2 , 12^2 , 13^2 , 15^2 , 17^2 , 18^2 , 19^2 $

[pal702004]

Подскажете ми- освен метода на налучкването какъв друг метод мога да използвам ?

Забавна е, но не за програмиране. Забелязали сте, че сбора на първите $18$ квадрата надхвърля $2018$.
$1^2+2^2+\cdots +18^2=2109$. Надхвърля го с $91$. Значи, с $18$ квадрата не може. Вашето решение, доколкото виждам е да махате от тези квадрати. $91$ е лошо в това отношение число (има и по-лоши).
Логичния въпрос е, като не може с $18$, няма ли да може със $17$. Варианти:
- да махнем едно от тези числа - не става
- да махнем две и да добавим едно (по-голямо от $18$)

$2109-x^2-y^2+z^2=2018$. Или

$x^2+y^2=z^2+91$, където $x<y \le 18,\;\;z>18$

Още при $z=19$ имаме късмет. Други решения (със $17$ събираеми май няма).

[peyo]

Подскажете ми- освен метода на налучкването какъв друг метод мога да използвам ?

Забавна е, но не за програмиране. ...

Напротив, това с се оказа много интересна задача за програмиране. Намерих ново много по-добро решение откъм време и памет, което първо дава най-дългата редица , а след това по странна логика и други решенияя, но не всички:

Код: Избери целия код

def search(i, numbers,s):
   if s==2018:
      print(len(numbers), numbers)
      return
   elif s>2018:
      return
   for k in range(1,3):
      search(i+k, numbers + [i+k], s + (i+k)**2)

search(0,[],0)


17 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 18, 19]
16 [1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 16, 18, 20]
15 [1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 15, 17, 19, 21]
14 [1, 2, 3, 4, 5, 7, 9, 11, 13, 14, 16, 17, 19, 21]
15 [1, 2, 3, 4, 6, 7, 8, 10, 12, 13, 14, 16, 17, 18, 19]
14 [1, 2, 3, 4, 6, 7, 9, 10, 12, 14, 16, 18, 19, 21]
15 [1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 14, 16, 17, 18, 20]
15 [1, 2, 3, 5, 7, 8, 9, 10, 11, 13, 14, 15, 17, 18, 19]
15 [1, 2, 4, 5, 6, 8, 9, 10, 11, 12, 14, 16, 17, 18, 19]
15 [1, 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 18, 20]
14 [1, 2, 4, 6, 7, 8, 9, 11, 12, 14, 16, 17, 19, 20]
14 [1, 2, 4, 6, 8, 9, 10, 11, 13, 14, 16, 17, 18, 19]
14 [1, 3, 4, 5, 6, 8, 10, 11, 12, 14, 16, 17, 19, 20]
13 [1, 3, 4, 6, 8, 10, 11, 13, 14, 16, 17, 19, 20]
13 [1, 3, 5, 6, 8, 9, 11, 12, 14, 16, 18, 19, 20]
13 [1, 3, 5, 6, 8, 9, 11, 13, 14, 15, 17, 19, 21]
14 [2, 3, 4, 6, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19]
13 [2, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21]
14 [2, 3, 5, 6, 7, 8, 9, 11, 12, 13, 15, 17, 19, 21]
14 [2, 3, 5, 6, 7, 9, 10, 12, 13, 14, 15, 16, 18, 20]
14 [2, 3, 5, 6, 8, 9, 10, 11, 12, 14, 15, 17, 18, 20]
13 [2, 3, 5, 7, 8, 10, 11, 12, 14, 16, 17, 19, 20]
13 [2, 3, 5, 7, 9, 10, 11, 12, 13, 15, 17, 19, 21]
15 [2, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18]
14 [2, 4, 5, 6, 7, 8, 10, 11, 13, 14, 15, 17, 18, 20]
13 [2, 4, 5, 6, 8, 9, 11, 13, 14, 16, 17, 19, 20]
12 [2, 4, 5, 7, 9, 11, 12, 14, 16, 18, 19, 21]

[peyo]

[..Намерих ново много по-добро решение откъм време и памет, което първо дава най-дългата редица , а след това по странна логика и други решенияя, но не всички:

Код: Избери целия код

def search(i, numbers,s):
   if s==2018:
      print(len(numbers), numbers)
      return
   elif s>2018:
      return
   for k in range(1,3):
      search(i+k, numbers + [i+k], s + (i+k)**2)

search(0,[],0)


Намерих проблема. Ето програмата която ще даде всички решения:

Код: Избери целия код

def search(i, numbers,s):
   if s==2018:
      print(len(numbers), numbers)
      return
   elif s>2018 or i>44:
      return
   search(i+1, numbers +[i+1], s + (i+1)**2)
   search(i+1, numbers, s)
   
search(0,[],0)

[ptj]

Намереното решение с 17 числа е единствено:
[tex](1,2,3,4,5,6,7,8,9,10,11,12,13,15,16,17,18,19)[/tex]

https://www.wolframalpha.com/input?i2d=true&i=solve+Power%5Bx%2C2%5D%2BPower%5By%2C2%5D%3DPower%5Bz%2C2%5D%2B91+%5C%2844%29+0%3Cx%3Cy%3C19%5C%2844%29+z%3E18++in+integer

[pal702004]

Намереното решение с 17 числа е единствено:
[tex](1,2,3,4,5,6,7,8,9,10,11,12,13,15,16,17,18,19)[/tex]

$16$ не трябва да е там.

Иначе да, но все пак трябва да се проверят и възможностите:

$x^2+y^2+z^2=u^2+v^2+91,\;\; x<y<z \le 18, 19 \le u<v$

поне заради това, че $18^2+17^2+16^2>19^2+20^2+91$

Проверил съм го, няма решение с махане на 3 и добавяне на 2 числа. С 4-3 вече сбора вдясно е по-голям

[ptj]

Да, заменяме 14 и 16 с 19.

Явно не си видял линка.