Две олимпиадные задачи на неравенства в целых числах

[yurasmolensk43]

1) Процент числа участников конкурса скрипачей, не прошедших на второй тур, заключен между 9,1% и 9,8%. Какое минимальное количество участников конкурса могло быть на первом туре?

2) На выборах кандидат получил от 50,332% до 50,333% голосов. Какое при этом могло быть наименьшее число избирателей?

В первой задаче можно составить числовое неравенство: $(1000a/91)<b<(1000a/98)$, где a - число участников, не прошедших на второй тур, а b - число участников первого тура соответственно. Перебирая значения а от 1 до много уже при $а=2$ получаем ответ - $b=21$.

Но вот вопрос - можно ли решить эту задачу без подбора? Все найденный мной решения основаны только на подборе, причем таком же. А как быть с числами, как во второй задаче? Такое без калькулятора за две минуты не посчитаешь

[DeBill]

yurasmolensk43
Посмотрим внимательно на Ваше решение первой задачи. Изначально у Вас было неравенство типа $k_1b<a<k_2b$ с малыми числами $k_i$. Вы переписали его иначе, в виде $K_2a<b<K_1a$, с большими $K_i=\frac{1}{k_i}$. Очень хорошо. Реально, эти $K_i$ равны $10+m_i$, где $m_i$ - малы. Вычитая из Вашего неравенства по $10a$, и полагая $c=b-10a$, получим задачу, аналогичную исходной. Процесс далее надо повторять, пока не получим интервал $(K_1,K_2)$, содержащий целые числа; наименьшее из них и даст (после обратной раскрутки) ответ (в первой задаче, это и получится уже на втором шаге; во второй надо помучиться подольше).
Отдельный вопрос - почему это и даст наименьшее решение: надо взять любое другое, и, начиная с последнего шага, проверить это....

[provincialka]

Я попробовала использовать цепные дроби. Вычисляем их до первого расхождения:

$$0,50332=[0;1,1,74,1,4,...]$$

$$0,50333=[0;1,1,74,1,1,...]$$

Между этими двумя числами находятся дроби

$$[0;1,1,74,1,2]=\frac{227}{451}=0,503322259...$$

$$[0;1,1,74,1,3]=\frac{303}{602}=0,503325942...$$

Число $n=451$ и будет искомым ответом.

[StaticZero]

provincialka, я впечатлён. Появился повод узнать, что такое цепные дроби.

[provincialka]

Ну... это не совсем решение... Оно дает пример подходящего $n$, но нет уверенности в его минимальности...
То есть в данном случае ответ $451$ действительно минимальный... Но я не проверяла в общем виде...
Более того, что делать, если первое различие между элементами составляет 1?

-- 11.11.2018, 21:53 --

Если цепные дроби имеют вид $[a;b,c,...]$ и $[a;b,c+1,...]$, то решение дается дробью $[a;b,c+1]$, а если разные числа стоят на нечетном месте, то выбирать надо меньшее.
Правда, эти дроби дадут решение, вообще говоря, нестрогих неравенств.

[yurasmolensk43]

yurasmolensk43 в сообщении #1353356 писал(а):

$(1000a/91)<b<(1000a/98)$

Прошу прощения, здесь, конечно же, левую и правую часть нужно поменять местами.

[provincialka]

Не уверена в своих рассуждениях... Надо это додумывать...
Но в конкретной задаче цепные дроби могут дать некий ориентир.

[DeBill]

provincialka в сообщении #1353402 писал(а):

Не уверена в своих рассуждениях... Надо это додумывать...

Ну, та схема, что я описал - это оно и есть - разложение в цепную дробь (я просто это страшное слово опустил). А док-во минимальности - должно получаться по той же схеме...
Забавно: задачи такого типа появились в ЕГЭ где то лет 5-7 назад. А до этого - теория чисел, делимость, факториалы...
Похоже, сочинители С6 постепенно всякие идеи из вышки и олимпиадных задач перетаскивают в школу... Что будет дальше? Раскраски? Инварианты? Игры? Графы? Крутая комбинаторика?

[StaticZero]

DeBill в сообщении #1353420 писал(а):

Что будет дальше? Раскраски? Инварианты? Игры? Графы? Крутая комбинаторика?

Там в один из годов кажется ВТФ просили доказать.

[Grom Hellscream]

StaticZero в сообщении #1353421 писал(а):

DeBill в сообщении #1353420 писал(а):

Что будет дальше? Раскраски? Инварианты? Игры? Графы? Крутая комбинаторика?

Там в один из годов кажется ВТФ просили доказать.

Даже не знаю, кем нужно быть, чтобы в такое верить .

[StaticZero]

Grom Hellscream, смелее же, сударь, кем же?

Вообще шутки шутками, а в сборниках попадается лажа вроде такой и такой, да тысячи их. Оно, конечно, как правило, связано с опечатками и/или дуростью придумщиков задач, но иногда всплывают и реальные свидетельства попадания такой лажи в реальные КИМы.

[Grom Hellscream]

StaticZero в сообщении #1353430 писал(а):

Grom Hellscream, смелее же, сударь, кем же?

Вообще шутки шутками, а в сборниках попадается лажа вроде такой и такой, да тысячи их. Оно, конечно, как правило, связано с опечатками и/или дуростью придумщиков задач, но иногда всплывают и реальные свидетельства попадания такой лажи в реальные КИМы.

Давайте я щас по-быстренькому сварганю вариант егэ с такииими задачами. Может даже сборник, была бы возможность издаваться в соответствующих книжных домах. Это на тему того как на dxdy ссылки с пикабу приводить, ага.
А если серьезно, то на реальных вариантах егэ и "рекомендованных" книгах для подготовки такой лажи нет, все задачи более чем решаемы школьником. И насчет "тысяч их" пруфов хотелось бы.

(Оффтоп)

Не считая того, что коль скоро требуемые знания для решения егэ размыты, то можно приколоться и задачу с теоремой Ферма решить, сославшись на нее и сказать "решений нет".

[DeBill]

Grom Hellscream в сообщении #1353469 писал(а):

на реальных вариантах егэ и "рекомендованных" книгах для подготовки такой лажи нет

В одной из таких книжек, в разделе "Задачи для самостоятельного решения", я встретил задачу "Решить уравнение в целых числах $2^x+3^y=5^z$"...

[Grom Hellscream]

DeBill в сообщении #1353490 писал(а):

Grom Hellscream в сообщении #1353469 писал(а):

на реальных вариантах егэ и "рекомендованных" книгах для подготовки такой лажи нет

В одной из таких книжек, в разделе "Задачи для самостоятельного решения", я встретил задачу "Решить уравнение в целых числах $2^x+3^y=5^z$"...

Но всяко же не теорема Ферма или нерешенная проблема. Да, задача гораздо сложнее типичного уровня С6, но тем не менее, вполне решаема школьником (хотя не уверен, что "обычный", сильно не знакомый со школьной теорией чисел сможет решить ее). И все-таки, на реальных вариантах егэ, за все 10-15 лет вроде бы даже таких задач не было.

[wrest]

DeBill в сообщении #1353490 писал(а):

В одной из таких книжек, в разделе "Задачи для самостоятельного решения", я встретил задачу "Решить уравнение в целых числах $2^x+3^y=5^z$"...

А в чем там лажа? Сразу видно два решения: помимо тривиального $x=1;y=1;z=1$ есть ещё не менее тривиальное $x=4;y=2;z=2$ .