[G.....n]

Mamy n monet, z czego k jest identycznych i fałszywych. k < n. Fałszywa moneta ma masę będąca efektem mnożenia masy prawdziwej monety przez liczbę niewymierną. Jaka jest minimalna liczba ważeń doskonałą wagą szalkową, by znaleźć 1,2,3,4,...,k fałszywych monet?
#matematyka

[baltazarbaltazarowiczzewakin]

@Ginden: Powiem Ci kurcze, że nie wiem. No kurcze nie wiem. Daj następne...

[G.....n]

@baltazarbaltazarowiczzewakin:

Daj następne

Proszę:

- PlecSchrodingera lubi, gdy liczba kupionych przez niego kromek chleba tostowego jest podzielna przez 2k, bo ma taki toster.

50% bochenków w sklepie ma n kromek, 25% ma n+1, 25% ma n-1.

Jeśli @PlecSchrodingera kupuje m bochenków, to jaką jest szansa, że liczba kromek będzie podzielna przez 2k?

http://www.wykop.pl/wpis/11935019/plecschrodingera-lubi-gdy-liczba-kupionych-przez-n/

[baltazarbaltazarowiczzewakin]

@Ginden: Ale nie ma takich tosterów :(

[G.....n]

@baltazarbaltazarowiczzewakin: Może coś prostego?
http://www.wykop.pl/wpis/6212144/dawalem-kiedys-zagadke-na-strimsie-ale-nikt-nie-ud/

[V.....d]

@Ginden: kiedyś chyba wrzuciłem identyczna lub bardzo podobna zagadkę pod #zagadkivorlanda. Znalezienie jeden fałszywej nie jest problemem i można to wykonać chyba w 3 krokach. Co do chleba - pokroić wzdłuż i zawsze ma parzysta liczbę kromek

[baltazarbaltazarowiczzewakin]

@Ginden: Nie mam głowy teraz do takich zagadek i słaby jestem z kombinatoryki, ale zadania bardz fajne i ciekawe. Skąd je masz?

[G.....n]

Znalezienie jeden fałszywej nie jest problemem i można to wykonać chyba w 3 krokach.

@Vorland: Dla n = 2000?

Skąd je masz?

@baltazarbaltazarowiczzewakin: Wymyślam w toalecie.

[V.....d]

@Ginden: tu juz mamy losowosc przy dzieleniu tego zbioru na pół, można to zoptymalizować, ale nigdy nie poświęciłem zbyt wiele czasu na to zagadnienie.

Problemem nie jest znalezienie jednej, ale np parzyste liczby trafnych monet i wtedy trzeba wykonać jeden krok więcej przy wazeniu

[G.....n]

@Vorland: Ogólnie intuicja podpowiada mi, że to można doprowadzić do problemu plecakowego.

[beniamin-k]

@Ginden: ale k != n/2, bo wtedy nie ma rozwiązania

[G.....n]

@beniamin-k: Bardzo ładne znalezienie edge case.

[beniamin-k]

@Ginden: Nie edge, tylko specific :) bo każda inna liczba jest rozwiązywalna :)

[Golob]

@Ginden: można też bez starty ogólności założyć że k<n/2