Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 75

GATE

У Мала есть книжка-раскраска, в которой каждая английская буква нарисована два раза. Она хочет раскрасить каждый из этих 52 отпечатков одним из k цветов, чтобы пары цветов, используемые для окраски любых двух букв, были разными. Оба отпечатка письма также могут быть окрашены в один и тот же цвет. Какое минимальное значение k удовлетворяет этому требованию?
(А) 9
(Б) 8
(С) 7
(D) 6

Ответ: (с)
Пояснение: Этот вопрос немного двусмысленный. Итак, сначала давайте поймем, какой вопрос задает. Таким образом, в книге у нас есть буквы AZ, и каждая буква печатается дважды, то есть 52 буквы. Теперь мы должны раскрасить каждую букву, поэтому нам нужна пара цветов, потому что каждая буква печатается дважды. Также в паре оба цвета могут быть несколько. Теперь условие состоит в том, что пару цветов нельзя использовать более одного раза.

Предположим, что у Мала есть 3 цвета: красный, синий, зеленый. Цвет может быть следующим: (A, A): (красный, красный), (B, B): (синий, синий), (C, C): (зеленый, зеленый), (D, D): (красный (Синий), (E, E): (красный, зеленый), (F, F): (синий, зеленый).
Теперь у нас не осталось больше пар цветов, мы использовали все пары, но могли раскрасить только 6 букв из 26. Поэтому вопрос в том, чтобы найти минимум №. цветов, чтобы мы могли раскрасить все 26 букв.

Так что, если у Малая есть k цветов, она может иметь k пар одинаковых цветов, таким образом раскрашивая k букв, тогда k C 2 другие пары цветов, таким образом, окраска k C еще 2 буквы.
Итого нет. цветных букв = k + k C 2 = k + k ( k — 1 ) 2 = k ( k + 1 ) 2 .
Итак, мы хотим, чтобы k ( k + 1 ) 2 ≥ 26, т.е. k ( k + 1 ) ≥ 52 , поэтому k ≥ 7 , поэтому вариант (C) является правильным.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2004 | Вопрос 75

0.00 (0%) 0 votes