Десять правильных дробей

[gipokrat]

Найдите наименьшее натуральное число $N$, для которого существуют десять положительных несократимых правильных дробей, удовлетворяющих следующим условиям:

1. Их произведение равно $\frac{1}{10}$.
2. Все двадцать числителей и знаменателей попарно различны.
3. Ни один числитель и ни один знаменатель не превосходит $N$.

[wrest]

gipokrat в сообщении #1735579 писал(а):

Все двадцать числителей и знаменателей попарно различны.

Это немного неясно, например:

? a=vecprod([1, 3, 5, 7, 8, 11, 13, 16, 17, 19])
%1 = 620780160
? b=vecprod([2, 4, 6, 10, 11, 13, 14, 17, 19, 20])
%2 = 6207801600
? c=a/b
%3 = 1/10
?

Тут некоторые числители равны некоторым знаменателям, но числители и знаменатели попарно различны.

[Gagarin1968]

wrest в сообщении #1735588 писал(а):

Тут некоторые числители равны некоторым знаменателям

Этого никак не может быть, ибо сказано в Писании условии:

gipokrat в сообщении #1735579 писал(а):

Все двадцать числителей и знаменателей попарно различны.

То бишь все 20 натуральных чисел различны.

[wrest]

Gagarin1968 в сообщении #1735590 писал(а):

То бишь все 20 натуральных чисел различны.

А... ну тогда всё плохо

[gris]

а чего сразу десять? Начнём с одной дроби:
$N(1)=10: \frac 1{10}=\frac1{10}.$
$N(2)=6: \frac 3{5}\cdot\frac16=\frac1{10}.$
$N(3)=20: \frac 3{20}\cdot\frac57\cdot\frac{14}{15}=\frac1{10}.$

[wrest]

========================================
  РЕШЕНИЕ НАЙДЕНО!
========================================
N = 27
Правильные пары (числитель / знаменатель):
   1 / 2    (gcd = 1)
   3 / 4    (gcd = 1)
   5 / 6    (gcd = 1)
   7 / 8    (gcd = 1)
   9 / 10   (gcd = 1)
  11 / 13   (gcd = 1)
  15 / 22   (gcd = 1)
  16 / 21   (gcd = 1)
  24 / 25   (gcd = 1)
  26 / 27   (gcd = 1)

prod(A) = 1556755200
prod(B) = 15567552000
prod(B) / prod(A) = 10
Уникальных чисел: 20
Время: 29.803000000000000000000000000000000000 с
========================================
time = 29,181 ms.
?

Код:

(Оффтоп)

\\ ==================== ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ ====================
G_N = 0;
G_sig = vector(35);
G_S = vector(20);
G_B = vector(10);
G_Bc = 0;
G_pB = 1;
G_tPB = 1;
G_found = 0;
G_fA = vector(10);
G_fB = vector(10);
G_adj = vector(10);
G_mt = vector(10);
G_lc = 0;

\\ ==================== СИГНАТУРЫ (XOR по чётности степеней простых) ====================
init_sigs(N) = {
  my(pr = [2,3,5,7,11,13,17,19,23,29,31]);
  for(x = 1, N,
    my(s = 0, n = x);
    for(i = 1, #pr,
      my(v = 0);
      while(n % pr[i] == 0, v++; n \= pr[i]);
      if(v % 2, s += 2^(i-1));
    );
    G_sig[x] = s;
  );
}

\\ ==================== ПРОВЕРКА И ЗАПОМИНАНИЕ ПАРОСОЧЕТАНИЯ ====================
G_match = vector(10);

search_match(i) = {
  if(i > 10, return(1));
  for(k = 1, #G_adj[i],
    my(b = G_adj[i][k]);
    if(!G_mt[b],
      G_mt[b] = 1;
      G_match[i] = b; \\ ЗАПОМИНАЕМ ИНДЕКС ПАРЫ
      if(search_match(i + 1), return(1));
      G_mt[b] = 0;
    );
  );
  0;
}

check_matching(A, B) = {
  for(i = 1, 10,
    G_adj[i] = select(j -> A[i] < B[j] && gcd(A[i], B[j]) == 1, [1..10]);
  );
  G_mt = vector(10);
  search_match(1);
}

\\ ==================== ПОИСК ПОДМНОЖЕСТВА B В S ====================
search_B(idx) = {
  if(G_found, return(1));
  if(G_Bc == 10,
    if(G_pB == G_tPB,
      my(A = vector(10), ia = 1, ib = 1);
      for(i = 1, 20,
        if(ib <= 10 && G_S[i] == G_B[ib],
          ib++;
        ,
          A[ia] = G_S[i];
          ia++;
        );
      );
      if(check_matching(A, G_B),
        G_found = 1;
        G_fA = A;
        G_fB = Vec(G_B);
        return(1);
      );
    );
    return(0);
  );
  if(idx > 20, return(0));
  if(10 - G_Bc > 21 - idx, return(0));

  my(val = G_S[idx]);
  my(np = G_pB * val);
  if(np > G_tPB, return(0));

  if(G_tPB % np == 0,
    G_B[G_Bc + 1] = val;
    G_Bc++;
    my(old = G_pB);
    G_pB = np;
    if(search_B(idx + 1), return(1));
    G_pB = old;
    G_Bc--;
  );
  if(search_B(idx + 1), return(1));
  0;
}

\\ ==================== ПОИСК МНОЖЕСТВА S ====================
search_S(idx, cnt, cx) = {
  if(G_found, return(1));
  if(cnt == 20,
    G_lc++;
    if(cx == 5,
      my(ps = 1);
      for(i = 1, 20, ps *= G_S[i]);
      my(P = 10 * ps);
      my(PB = sqrtint(P));
      if(PB * PB == P,
        G_tPB = PB;
        G_Bc = 0;
        G_pB = 1;
        if(search_B(1), return(1));
      );
    );
    return(0);
  );
  if(G_N - idx + 1 < 20 - cnt, return(0));

  G_S[cnt + 1] = idx;
  if(search_S(idx + 1, cnt + 1, bitxor(cx, G_sig[idx])), return(1));
  if(search_S(idx + 1, cnt, cx), return(1));
  0;
}

\\ ==================== ГЛАВНАЯ ФУНКЦИЯ ====================
find_solution() = {
  my(t0 = getwalltime());
  print("========================================");
  print("  Поиск наименьшего N для 10 дробей");
  print("  Алгоритм: XOR-фильтр + backtracking");
  print("========================================\n");

  for(N = 20, 35,
    G_N = N;
    G_found = 0;
    G_lc = 0;
    init_sigs(N);

    my(t1 = getwalltime());
    search_S(1, 0, 0);
    my(dt = (getwalltime() - t1) / 1000.0);

    if(G_found,
      print("\n========================================");
      print("  РЕШЕНИЕ НАЙДЕНО!");
      print("========================================");
      print("N = ", N);
      
      \\ Формируем правильный вывод пар на основе найденного паросочетания
      print("Правильные пары (числитель / знаменатель):");
      for(i = 1, 10,
        my(a = G_fA[i]);
        my(b = G_fB[G_match[i]]);
        printf("  %2d / %-2d   (gcd = %d)\n", a, b, gcd(a, b));
      );
      
      my(pa = 1, pb = 1);
      for(i = 1, 10, pa *= G_fA[i]; pb *= G_fB[i]);
      print("\nprod(A) = ", pa);
      print("prod(B) = ", pb);
      print("prod(B) / prod(A) = ", pb / pa);
      print("Уникальных чисел: ", #Set(concat(G_fA, G_fB)));
      print("Время: ", (getwalltime() - t0) / 1000.0, " с");
      print("========================================");
      return(N);
    );
    print("N = ", N, ": решений нет  (", dt, " с, ", G_lc, " кандидатов)");
  );
  print("\nРешение не найдено в диапазоне 20..35.");
}

find_solution();