Нетипична задача

[ins-]

Имаме [tex]n[/tex] [tex](n \ge 2)[/tex] числа, които трябва да се подредят в таблица с [tex]k[/tex] [tex](k\ge 2)[/tex] колони така, че в [tex]k-1[/tex] колони да имаме по равен брой числа, а в оставащата колона да имаме поне едно число, но не повече числа, отколкото в останалите колони. При какви условия за [tex]n[/tex] и [tex]k[/tex] е възможно да се направи споменатото подреждане?

[mkmarinov]

[tex]k \le n[/tex], k-1 не дели n?

[ins-]

И аз не знам отговора. Зададох си този въпрос, докато писах един попъп с чекбоксове.
По какъв път стигаш до тези изводи?

[martin123456]

Нека сме поставили в k-1 колони по x числа, а в последната колона y числа. По условие [tex]y \ge 1[/tex]. Пак по условие [tex]x\ge y[/tex]. Като преброим числата получаваме [tex](k-1)x+y=n[/tex]. Тъй като [tex]n=(k-1)x+y \ge yk \ge k[/tex] излиза, че [tex]n \ge k[/tex].
Според мен това е достатъчно.
Ето пример, който доказва моето предположение.
Избираме [tex]x=[\frac{n}{k}]+1[/tex]. Тогава [tex]y=n-(k-1)([\frac{n}{k}]+1)[/tex]. Трябва единсвено да проверим, че [tex]x\ge y[/tex]. Последното е еквивалентно на [tex][\frac{n}{k}]+1 \ge n-(k-1)([\frac{n}{k}]+1) \Leftrightarrow ([\frac{n}{k}]+1)k \ge n[/tex]. Но [tex][\frac{n}{k}] > \frac{n}{k}-1[/tex] и значи [tex]([\frac{n}{k}]+1)k>n[/tex].

[ins-]

Добър пример за проверка е n=19, k=6.

[martin123456]

Да, прав си, не е достатъчно, понеже не съм проверил [tex]y \ge 1[/tex].
Сега излиза, че [tex]x \le \frac{n-1}{k-1}[/tex].
Затова отговорът е следния
1. ако съществува цяло число [tex]x \in [\frac{n}{k},\frac{n-1}{k-1}][/tex], то се взима то
2. ако не съществува, то не може да направи това групиране

[ins-]

Сигурен ли си? Некъв хитър румънец каза, че НДУ е: [tex]{n-1 < k\lfloor (n-1)/(k-1)\rfloor}[/tex], но не знам доколко е прав.

[martin123456]

Мисля, че съм сигурен.

1. [tex]n\ge k[/tex] и ако съществува цяло число [tex]x \in [\frac{n}{k},\frac{n-1}{k-1}][/tex], то се взима то
2. [tex]n <k[/tex] или ако не съществува цяло число [tex]x \in [\frac{n}{k},\frac{n-1}{k-1}][/tex], то не може да направи това групиране

[ins-]

Имам тъп въпрос ... в 1. - възможно ли е да има повече от едно цяло число в този интервал?
Ако отговора е "не" - защо? Ако е "да" - кое от тях се взима? (n=1000 k=10)

[martin123456]

Няма значение кое число ще вземеш. Което и да вземеш пак ще работи. Може да има и повече от едно в този интервал.

[ins-]

При n=1000, k=10, ако взема 110 няма да работи, а принадлежи на интервала.

[martin123456]

защо да не работи
110,110,...,110,10

[ins-]

Прав си, работи. Това е интересно, че при посочените условия съществуват множество решения.

[georgi111]

Какво те учудва че има множество решения - свойства на числата и по скоро на решенията в н-торки на [tex]n = x_1 + ... + x_n[/tex]

[ins-]

Случва се човек да се обърка. А разсъжденията на Мартин даже дават отговор, ако задачата беше "Да се намери броя на възможните подреждания с посочените свойства."