Logikai feladat

Adott száz tégla, megszámozva, egyesével, egytől százig. Ezeket a téglákat különböző oszlopokba pakoljuk a következő szabály figyelembevételével: minden tégla száma nagyobb vagy egyenlő kell legyen, mint a rápakolt téglák számának összege.

Gy.K.: (az oszlopok az egyszerűség kedvéért fektetve...)

10 6 3 1 jó
10 8 1 jó
10 6 4 2 1 nem jó
10 9 8 nem jó

A kérdés az, hogy legkevesebb hány különböző oszlopba rendezve lehet lerakni mind a száz téglát? (Természetesen szükség esetén elképzelhetőek egy téglányi magas oszlopok.)

Lehet licitálni. :)

U.I.: Tessék logikusan megoldani. Aki géppel esne a feladatnak, azt is lehet, de akkor legyen 2^18 darab tégla. :p

( harlequin | 2009. 07. 30., cs – 15:52 )

elsore 30 jott ki, de ne tudom jol gondolkodtam-e, meg egyszer atgondolni lusta vagyok :)

( anr | 2009. 07. 30., cs – 18:32 )

34

3-al oszthatoak a 3+ elemek minden sorban :)
--
Live free, or I f'ing kill you.

Ez már jó fölső becslés, kézzel el lehet érni!

pl.:
1:1 2 3 6 12 24 48 96
2:4 5 9 18 36 72
3:7 8 15 30 60
4:10 11 21 42 84
5:13 14 27 54
6:16 17 33 66
7:19 20 39 78
8:22 23 45 90
9:25 26 51
10:28 29 57
11:31 32 63
12:34 35 69
13:37 38 75
14:40 41 81
15:43 44 87
16:46 47 93
17:49 50 99

és a kimaradt 33 elem meg ceil(34/2)==17 kupacba elfér párosával. De van-e jobb?

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

( strangelove | 2009. 07. 30., cs – 19:11 )

worst case complexity

a téglák számának a fele felfele kerekítve biztosan elegendő, hiszen ha sorba rendezzük a téglákat a rajtuk levő szám szerint, és egymás mellé teszük őket, akkor az új sorrend szerint minden páratlanadikra rárakható a mellette levő párosok közül a nemkisebbik.

Persze ez van, amikor éles, pl. ha minden tégla egyforma.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

( harlequin | 2009. 07. 30., cs – 19:42 )

n=100 teglanal:
(n-m)^2+(n-m) = (n^2+n)/2
vagyis
(100-m)^2+(100-m) = 5050
ebbol m=30... ennel kevesebb nem lehet

az azt jelenti, hogy a foldon levo teglak a 71..100 ez osszesen 2565, az osszes tobbi meg 1..70, azaz 2485 -> tehat elmeletileg rafer, ha jol szet lehet osztani.

... viszont megprobaltam lerajzolni, ott meg ugy jott ki hogy az egyharmada, vagyis esetunkben kb. 33 :P

Harminc, éles az alsó becslés:

100 41 39 20
99 42 38 18
98 43 37 16
97 44 36 14
96 45 35 12
95 46 34 10
94 47 33 8
93 48 32 6
92 49 31 4
91 50 40
90 51 30 2
89 52 29
88 53 28
87 54 27
86 55 26
85 56 25
84 57 24
83 58 23
82 59 22
81 60 21
80 61 19
79 62 17
78 63 15
77 64 13
76 65 11
75 66 9
74 67 7
73 68 5
72 69 3
71 70 1

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne