Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

27. Капля чернил

На бесконечный белый лист уронили каплю чернил, которая превратилось во множество разбросанных пятен неправильной формы с общей площадью <1. Как покрыть этот лист бумаги квадратной сеткой с шагом 1, чтобы ни один узел сетки не попал в чернильное пятно?
2006-11-23

Обсуждение


Задачи :: Капля чернил
↓↓ 0 ↑↑   eruditor.ru (118 / 227)   2007-01-26 18:17   »»


Я может чего не понимаю в условиях задачи, мы берем воображаемую сетку и начинаем двигать её по листу. Решение либо находится, либо нет. В чем суть задачи?
↓↓ 0 ↑↑   Китаец (0 / 12)   2007-05-01 07:16   «« #2 »»   Ответить


Да тоже не понятно
Если лист бесконечный, а капля не может разлететься бесконечно, то можно выбрать такую клетку сетки в которую попадет вся разбрызганная капля
↓↓ 0 ↑↑   Balamut (5 / 14)   2007-05-08 14:00   «« #3 »»   Ответить


Сорри про шаг в 1 забыл
↓↓ 0 ↑↑   Balamut (5 / 14)   2007-05-08 14:01   «« #4 »»   Ответить


начинаем сетку именно с квадрата где и есть разбрызганная капля. находим место, где нет капли чернил (такое место обязательно должно быть) ставим там точку - это и есть первый узел сетки, и пошли дальше с шагом в 1. так как сказано, что пянто не должен попасть ни на один узел, у нас так и получится.
↓↓ 0 ↑↑   JJ (0 / 1)   2007-05-08 21:56   «« #5 »»   Ответить


> //Китаец : Я может чего не понимаю в условиях задачи, мы берем воображаемую сетку и начинаем
> двигать её по листу. Решение либо находится, либо нет. В чем суть задачи?
Суть в том, чтобы ДОКАЗАТЬ, что решение найдется.
> //JJ: так как сказано, что пянто не должен попасть ни на один узел, у нас так и получится.
Сильно! :)
На самом деле можно выбрать такую решетку ("сетку") в любом направлении.
↓↓ 0 ↑↑   LH (0 / 3)   2007-05-12 23:32   «« #6 »»   Ответить


Надо все чернильные капли перенести в единичный квадрат.
Напомним, что целая часть х [x]-это наибольшое
целое число, которое не превышает x.
Дробная часть x, {x}=x-[x], 0<={x}<=1.
Зафиксируем декартовую систему координат.
Для каждой чернильной точки (x, y) построим
точку ({x}, {y}) и сделаем ее черной.
Площадь капли меньше 1,
поэтому площадь "новых" точек тоже меньше 1.
Поэтому существует белая точка (a, b), 0<=a, b<=1.
Пусть эта точка будет узлом сетки.
↓↓ 0 ↑↑   2+2=5 (0 / 3)   2007-11-24 03:25   «« #7 »»   Ответить


брызги
а разве сказано что брызги лежат в пределах единичного квадрата?
↓↓ 0 ↑↑   Archery (0 / 4)   2008-10-14 19:02   «« #8 »»   Ответить


от обратного
... может следует предположить, что есть такое невозможно, тогда задача мне кажется решаемая, т.е. чтобы это условие удовлетворилось, необходимо чтобы на окружности еденичного радиуса не было "просветов". Но мы можем сместить узел сетки в сторону, следовательно сдвигая эту точку на некое расстояние, мы должны для удовлетворения этого условия заполнить некую площадь... по моим соображениям она будет больше еденицы.. но скорее всего при точном решении окажется равной 1
↓↓ 0 ↑↑   FoG (0 / 6)   2008-10-31 17:56   «« #9 »»   Ответить


Сетку расположить нельзя.
Если условно взять крайность хотя бы такую как:
Да, общая площадь капель меньше одного или даже одной - не важно. Площадь значения не имеет, так как площадь это перемноженные длины сторон (представим каплю квадратной(она ведь непроизвольной формы)). Существует такая возможность 2*[число<0.5]. Вот и всё, Порог одной длины (2) больше порога сетки (1). Наложить невозможно. Если только не расставить эти капли специально.
↓↓ 0 ↑↑   Tim (0 / 4)   2009-01-17 21:37   «« #10 »»   Ответить


Все проще)) сетку можно наложить на обратной стороне листа))
↓↓ 0 ↑↑   Алексей (10 / 18)   2017-08-13 23:45   «« #16 »»   Ответить


Здесь сетку в любом случае можно расположить как требуют по условию.
доказывается это логическими выводами и рассуждениями, навермо аналогично задачам раскраскам что можно расположить бесконечно много точек на растоянии корень из 2 и 1 с ограничением по площади одного цвета. но я физик , так что мне щас немного лень думать над этой довольно нудноу задачей %)
↓↓ 0 ↑↑   Givchik3316 (0 / 31)   2009-08-09 13:39   «« #11 »»   Ответить


...
недостаточно выбрать только один узел, ибо на радиусе 1 от нее может быть расположена чернильная окружность-кольцо небольшой площади. Думается надо оперировать площадями и равнобедренными треугольниками стороной 1
↓↓ 0 ↑↑   Blabber (0 / 14)   2011-01-08 22:38   «« #12 »»   Ответить


Не все поймут но кто поймет, тот оценит.
Вообще то решение с дробной частью - по моему правильное но ладно... Предположим декартова система координат уже нанесена и нам нужно сделать парралельный перенос координатной сетки, чтобы ни в одну вершину узла не попало пятно. Предположим что координатная плоскость - абсолютно прозрачный бесконечный лист толщины 0. Возьмем каждый из квадратиков 1на1 и положим друг на друга с сохранением заданной ориентации и посмотрим на бесконечно удаленный источник света. Если бы мы не увидели свет то это значило бы что проэкция пятна из всех квадратиков на один не меньше единицы, а, значит, и площадь самого пятна не меньше единицы, что противоречило бы условию задачи.Значит мы увидим свет в точке с координатами (x,y): 0<x<1 0<y<1. Сделав парралельный перенос первоначальной системы координат на вектор (x,y)получим искомую(систему координат.
↓↓ 0 ↑↑   crapal (0 / 1)   2011-03-23 23:33   «« #13 »»   Ответить


мудизм)
площадь всей капли меньше одной! тогда че ваще думать? достаточно взять сетку квадрат которой будет покрывать все капли и все! там же не сказано сколько это "1" вот и все! можно вообще взять бесконечный квадрат размером с лист!)
↓↓ 0 ↑↑   lavsvip (-124 / 40)   2011-08-28 19:03   «« #14 »»   Ответить


Мы пойдём другим путём.
Нанести сетку на оборотную сторону листа.
↓↓ 0 ↑↑   Глеб (0 / 1)   2012-01-19 23:53   «« #15 »»   Ответить


По поводу обратной стороны листа у меня тоже мелькала мысль, но это все же не серьёзно.
Возьмем каплю, не квадратную (зачем?), круглую. Мысленно разместим в ней узел, и станем двигать сеть, пытаясь вывести узел за пределы капли, но так, чтобы соседние узлы сети не зашли в зону капли. Какой должен быть минимальный диаметр капли, чтобы этого не произошло?
r = √ (0,5^2 +0,5^2) = 0,35; Площадь капли S = 0,35^2*Pi = 0,39<1. Достаточно иметь как фрагмент каплю в форме окружности радиусом 0,39, чтобы сеть не попала хотя бы одним узлом в эту каплю.
↓↓ 0 ↑↑   Олег (0 / 85)   2018-10-06 16:13   «« #17 »»   Ответить


В расчетах ошибка. r = √ (1^2 + 1^2) / 2 = 0,707 S = 0,707^2*Pi = 1,57 > 1
Покрыть сетью можно. Если разбить пятно на 2 фрагмента площадью каждый чуть менее 0,5 и расположить каким-либо образом, но если диаметр пятен менее 1, их легко расположить между узлами. При S = 0,5 r = 0,707 < 1
↓↓ 0 ↑↑   Олег (0 / 85)   2018-10-06 21:48   «« #18   Ответить



Ваше имя
Email
Текст ответа
© 2006-2020   Авторы