Какое наименьшее число студентов могло быть в аудитории?

[gipokrat]

Преподаватель высшей математики Анастасия Фёдоровна вошла в аудиторию и, окинув взглядом ряды, заметила, что девушек в аудитории больше, чем $\dfrac{15}{28}$, но меньше, чем $\dfrac{22}{41}$ от общего числа присутствующих студентов.

Какое наименьшее число студентов могло быть в аудитории?

[ozheredov]

gipokrat, а откуда вообще говоря следует, что студентов должно быть целое число?

[gipokrat]

ozheredov в сообщении #1718345 писал(а):

gipokrat, а откуда вообще говоря следует, что студентов должно быть целое число?

Наверное, из соображений здравого смысла.
Их что, полтора или две трети может быть?

[Yadryara]

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

Какое наименьшее число студентов могло быть в аудитории?

69 вроде

[Null]

Цепные дроби:

$\frac{15}{28}=[0; 1, 1, 6, 2]$

$\frac{22}{41}=[0; 1, 1, 6, 3]$

ответ $\frac{37}{69}=[0; 1, 1, 6, 2, 2]$

[wrest]

Обозначим границы как $N\dfrac{p}{a}<G<N\dfrac{q}{b}; N,G \in \mathbb{N}$

(Оффтоп)

(в задаче получается $N\dfrac{15}{28}<G<N\dfrac{22}{41}; N,G \in \mathbb{N}$ и $N$ всего студентов а $ G$ - девушек).

Тогда легко видеть , что искомое $N\le \min \left \{a+b,\left \lceil \dfrac{ab}{qa-pb}\right \rceil \right \}$

(Оффтоп)

(в задаче получается $N\le \min \left \{69,1148 \right \}$)

Во всяком случае, количество студентов всегда не больше чем сумма знаменателей замеченных Анастасией Федоровной несократимых дробей.

[wrest]

Выдавил из ИИ алгоритм вычисления, сперва $O(N)$ затем $O(\log N)$ и наконец, похоже, $O(1)$

[Mihr]

(Оффтоп)

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

окинув взглядом ряды, заметила, что девушек в аудитории больше, чем $\dfrac{15}{28}$, но меньше, чем $\dfrac{22}{41}$ от общего числа присутствующих студентов

Забавная деталь подобных задач - вопрос: как можно получить столь точную оценку с одного взгляда?

[waxtep]

Mihr в сообщении #1718483 писал(а):

как можно получить столь точную оценку с одного взгляда?

анекдот про стадо овец и математика писал(а):

Элементарно! Я подсчитал число ног и поделил его на четыре

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

Их что, полтора или две трети может быть?

Если это занятие в медицинском ВУЗе, ...

[wrest]

Mihr в сообщении #1718483 писал(а):

Забавная деталь подобных задач - вопрос: как можно получить столь точную оценку с одного взгляда?

Отсюда прорастает другая задача. Допустим нам дана эта дробь 37/69 (это то что увидела Анастасия Фёдоровна, а увидела она это очень просто: известный ей списочный состав аудитории 70 чел., причем 37 дев. и 33 мал., и одного м. не было в аудитории). А какими свойствами обладают дроби 15/28 и 22/41 что вы назвали их "столь точной оценкой"?

[Mihr]

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

А какими свойствами обладают дроби 15/28 и 22/41 что вы назвали их "столь точной оценкой"?

Всё, что я имел в виду: искомое число $\dfrac{37}{69}$ покрыто интервалом, длина которого меньше одной тысячной: $\dfrac{22}{41}-\dfrac{15}{28}<0,001$.

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

увидела она это очень просто: известный ей списочный состав аудитории 70 чел., причем 37 дев. и 33 мал., и одного м. не было в аудитории

Ровно одного студента не было? И это возможно было определить с одного взгляда?

[wrest]

Mihr в сообщении #1718531 писал(а):

Ровно одного студента не было? И это возможно было определить с одного взгляда?

Можно если не было ну например старосты или кого-то другого "заметного".
Ну и - посчитать сколько присутствует можно вычитанием из известной емкости аудитории количества незанятых мест. Если аудитория на 70 мест то свободно одно -- изи

Да, я тут выдавил из ИИ обратный алгоритм: дана несократимая дробь, вычислить левую и правую от неё такие, что данная дробь имеет наименьший знаменатель между правой и левой (т.е. надо найти "правильных родителей" в дереве Фарея ака дереве Штерна-Броко).

Ну например, если девушек 40 из 69, то их больше чем 11/19 но меньше чем 29/50, и при таких границах наименьшее количество студентов -- 69

[Null]

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

$O(1)$

Мистика какая то. Можно узнать алгоритм?

-- Ср фев 18, 2026 20:13:48 --

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

Да, я тут выдавил из ИИ обратный алгоритм: дана несократимая дробь, вычислить левую и правую от неё такие, что данная дробь имеет наименьший знаменатель между правой и левой (т.е. надо найти "правильных родителей" в дереве Фарея ака дереве Штерна-Броко).

Алгоритм Эвклида?

[wrest]

Null в сообщении #1718546 писал(а):

Мистика какая то. Можно узнать алгоритм?

Хотя ИИ предполагает, что сложность $O(\log N)$, мои проверки показали, что для $N=10^6;10^7;10^8$ результат получается за то же количество итераций (три). Но вероятно, тут $N$ (искомый наименьший знаменатель для дроби лежащей между двумя данными дробями) не то, от чего зависит сложность алгоритма. Ну то есть, мне не удалось замерить зааисимость, потому написал, что

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

похоже, $O(1)$

Может там например $O(\log \log N)$...
Программа:

(Оффтоп)

1. farey_min(frac1, frac2) = { 
2. /* Находит дробь с минимальным знаменателем между frac1 и frac2 */ 
3. /* Сложность: O(log N) */ 
4.  
5.     my( 
6.         /* Входные дроби в виде числитель/знаменатель */ 
7.         a = numerator(frac1), b = denominator(frac1), 
8.         c = numerator(frac2), d = denominator(frac2), 
9.          
10.         /* Границы дерева Штерна-Броко */ 
11.         l_num = 0, l_den = 1,  /* левая граница: 0/1 */ 
12.         r_num = 1, r_den = 0,  /* правая граница: 1/0 (∞) */ 
13.          
14.         /* Текущая медианта */ 
15.         m_num, m_den, 
16.          
17.         /* Вспомогательные переменные для вычисления шага */ 
18.         num, den, k 
19.          
20.     ); 
21.      
22.     /* Упорядочиваем: гарантируем a/b < c/d */ 
23.     if (a*d > b*c, [a,b,c,d] = [c,d,a,b]); 
24.      
25.     while (1, 
26.         m_num = l_num + r_num; 
27.         m_den = l_den + r_den; 
28.          
29.         if (m_num * b <= a * m_den, 
30.             /* Медианта <= левой границы - прыгаем вправо */ 
31.             num = a*l_den - l_num*b; 
32.             den = r_num*b - a*r_den; 
33.             k = num \ den; 
34.             if (k == 0, k = 1); 
35.             l_num = l_num + k * r_num; 
36.             l_den = l_den + k * r_den; 
37.         , 
38.             if (m_num * d >= c * m_den, 
39.                 /* Медианта >= правой границы - прыгаем влево */ 
40.                 num = r_num*d - c*r_den; 
41.                 den = c*l_den - l_num*d; 
42.                 k = num \ den; 
43.                 if (k == 0, k = 1); 
44.                 r_num = r_num + k * l_num; 
45.                 r_den = r_den + k * l_den; 
46.             , 
47.                 /* Медианта внутри интервала - найдено! */ 
48.                 return (m_num / m_den); 
49.             ) 
50.         ) 
51.     ); 
52. } 

-- 18.02.2026, 23:08 --

Null в сообщении #1718546 писал(а):

Алгоритм Эвклида?

Разложение в непрерывную дробь и вычисление "родителей" в дереве Фарея. Сложность $O(L)$ где $L$ - длина разложения в непрерывную дробь (плюс само разложение, это встроенная функция, там не знаю, но вроде сложность логарифмическая) .
Программа:

(Оффтоп)

1. farey_parents(frac) = { 
2. /* Находит родительские дроби для ЛЮБОЙ дроби frac */ 
3. /* Возвращает [left, right] где left < frac < right */ 
4.     my(p = numerator(frac), q = denominator(frac)); 
5.    /* Раскладываем в непрерывную дробь */ 
6.     my(cf = contfrac(frac)); 
7.    /* длиной n */ 
8.     my(n = #cf); 
9.      
10.     /* Вычисляем все сходящие */ 
11.     my(pnm2 = 0, qnm2 = 1);  /* p₋₂/q₋₂ */ 
12.     my(pnm1 = 1, qnm1 = 0);  /* p₋₁/q₋₁ */ 
13.     my(pn, qn); 
14.      
15.     for(i = 1, n-1, 
16.         pn = cf[i]*pnm1 + pnm2; 
17.         qn = cf[i]*qnm1 + qnm2; 
18.         pnm2 = pnm1; qnm2 = qnm1; 
19.         pnm1 = pn;   qnm1 = qn; 
20.     ); 
21.      
22.     /* pnm1/qnm1 = предпоследнее сходящее */ 
23.     /* pn/qn = последнее сходящее = исходная дробь */ 
24.      
25.     pn = cf[n]*pnm1 + pnm2; 
26.     qn = cf[n]*qnm1 + qnm2; 
27.      
28.     /* Левый родитель = предпоследнее сходящее */ 
29.     my(left = pnm1/qnm1); 
30.      
31.     /* Правый родитель = (pn - pnm1) / (qn - qnm1) */ 
32.     my(right = (pn - pnm1) / (qn - qnm1)); 
33.      
34.     /* Упорядочиваем */ 
35.     if (left > right, [left, right] = [right, left]); 
36.      
37.     return ([left, right]); 
38. } 

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

[Null]

Сложность $\log N$- тестировать надо на дробях $\frac{F_{n-2}}{F_{n-1}},\frac{F_{n-1}}{F_{n}},\frac{F_{n-3}}{F_{n-2}}$ и $\frac{F_{n-3}}{F_{n-1}},\frac{F_{n-2}}{F_{n}},\frac{F_{n-4}}{F_{n-2}}$, где $F_{n}\approx N$